# Question
Title: Choice of algorithm for hierarchical clustering for minimizing network communication costs
Suppose I have a large distributed task running on a cluster system where part of the workload is compute bound and part depends on network performance. Data transfer is not completely homogeneous between processes - some communication pairs are more or less sensitive to bandwidth and latency than others.

We've profiled this and have a square matrix describing how much information is transferred between each pair of processes during the job.

We also know how the network is laid out and can approximate a scalar communication cost for each entry in that matrix.

Starting from that point, which clustering algorithms should I be looking at to permute that matrix to minimize total communication distance? Or, I think equivalently: how can I compute a near-optimal clustering of processes so that the processes that communicate the most are closest to each other on the network?

# Answer
This is a form of assignment problem; in particular, it is an instance of quadratic assignment problem. There are some known techniques available for solving this sort of problem.

## Using integer linear programming

One approach is to use integer linear programming.

Let $d\_{p,q}$ denote the amount of data communicated between processes $p$ and $q$, for each pair of processes $p,q$. Also, let $c\_{i,j}$ denote the communication cost for data sent between machines $i$ and $j$, for each pair of machines $i,j$. These are given.

The goal is to find an assignment of processes to machines, that minimizes the total communication cost. I'll assume that you only allow one process to be assigned to each machine. We can model this as follows. For each process $p$ and each machine $i$, let $x\_{p,i}$ be an unknown that is either 0 or 1, with the intent that $x\_{p,i}=1$ means process $p$ is assigned to machine $i$. You can force it to be 0 or 1 with the constraint $0 \le x\_{p,i} \le 1$. You can force each process to be assigned to one machine with the constraint

$$\sum\_i x\_{p,i} = 1.$$

You can also force each machine to be assigned at most one process with the constraint

$$\sum\_p x\_{p,i} \le 1.$$

The total communication cost is

$$\sum\_{p,q,i,j} x\_{p,i} x\_{q,j} c\_{i,j} d\_{p,q},$$

where the sum is over all $p\ne q$ and $i \ne j$. That's what we'd like to minimize.

This is not yet a linear objective function, so we can't apply integer linear programming directly, but we can transform it into an integer linear program as follows. Let $y\_{p,q,i,j} = 1$ if process $p$ is assigned to machine $i$ and process $q$ is assigned to machine $j$. We have $y\_{p,q,i,j} = x\_{p,i} \land x\_{q,j}$. Now logical AND can be expressed in an integer linear program by adding the constraints

$$y\_{p,q,i,j} \ge x\_{p,i} + x\_{q,j} - 1$$ $$y\_{p,q,i,j} \le x\_{p,i}$$ $$y\_{p,q,i,j} \le x\_{q,j}$$ $$0 \le y\_{p,q,i,j} \le 1.$$

With these extensions, the total communication cost becomes

$$\sum\_{p,q,i,j} y\_{p,q,i,j} c\_{i,j} d\_{p,q},$$

which *is* a linear function. Thus, you now obtain an integer linear program, where the goal is to minimize the total communication cost, subject to the constraints listed above. You could try solving it using an off-the-shelf integer linear programming (ILP) solver.

There is no guarantee that this will efficiently find an optimal solution -- after all, integer linear programming is NP-hard in the worst case -- but in practice ILP solvers often work surprisingly well on many problems. So, you could give it a try and see how well it works on your particular problem instances. I don't know if there is a better algorithm, but this is one approach you could try.

---

P.S. In fact, in this particular case, you could skip the constraints $y\_{p,q,i,j} \le x\_{p,i}$ and $y\_{p,q,i,j} \le x\_{q,j}$ without changing the final solution. This makes the program a little bit simpler, at the cost of making it a little harder to understand why it "works" correctly for your problem.

## Dedicated algorithms

An alternative is to use a dedicated algorithm for the quadratic assignment problem. For instance, Wikipedia mentions QAPLIB, a dedicated solver for instances of the quadratic assignment problem. You could try using QAPLIB on your problem instance, to see how well it works.

There may be other algorithms for the quadratic assignment problem -- I recommend doing a literature search to see what you can turn up.
> 2 votes

---
Tags: algorithms, graphs, computer-networks, weighted-graphs, assignment-problem
---


# Question
Title: Algorthm: Given a set of points, width around line, find line to capture maximum points
I want to know if there is an algorithm for this problem.

I have a list of points given as (x,y) values and a given distance. I want to draw a line through the set of data points so that the size of the set of points that is within the given distance from the line is maximized. That is, this line

Does an algorithm for this problem exist?

# Answer
If your notion of distance is "vertical distance", similar to how residuals are computed during ordinary linear regression, this problem can be solved with linear programming.

Let $y=ax+b$ be the equation of the desired line; here $a,b$ are unknowns. Suppose we are given a list of points $(x\_i,y\_i)$. The vertical distance from $(x\_i,v\_i)$ to the line $y=ax+b$ is

$$|ax\_i+b-y\_i|.$$

Suppose we want this distance to be at most $d$, where $d$ is given. In other words, we want

$$|ax\_i+b-y\_i| \le d.$$

This is equivalent to

$$y\_i-d \le ax\_i+b \le y\_i+d,$$

which gives two linear inequalities. (Recall that $x\_i,y\_i,d$ are known, and $a,b$ are unknown.) Given $k$ points, you get $2k$ linear inequalities. Now you can use linear programming to find $a,b$ that satisfy all of these linear inequalities.

You can even find the minimal value of $d$ such that such a line exists. Simply treat $d$ as an additional unknown, and minimize $d$ subject to the $2k$ linear inequalities above.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Shamos-Hoey Line segment intersection runtime
In the Shamos-Hoey algorithm for finding whether or not any two of $n$ line segments intersect, which is available at this site: http://geomalgorithms.com/a09-\_intersect-3.html, there is use of "nearest line above" and "nearest line below". The algorithm is supposed to run in time $O(n\log n)$. Here is their pseudocode:

```
Initialize event queue EQ = all segment endpoints;
Sort EQ by increasing x and y;
Initialize sweep line SL to be empty;

While (EQ is nonempty) {
    Let E = the next event from EQ;
    If (E is a left endpoint) {
        Let segE = E's segment;
        Add segE to SL;
        Let segA = the segment Above segE in SL;
        Let segB = the segment Below segE in SL;
        If (I = Intersect( segE with segA) exists)
            return TRUE;   // an Intersect Exists
        If (I = Intersect( segE with segB) exists)
            return TRUE;   // an Intersect Exists
    }
    Else {  // E is a right endpoint
        Let segE = E's segment;
        Let segA = the segment above segE in SL;
        Let segB = the segment below segE in SL;
        Delete segE from SL;
        If (I = Intersect( segA with segB) exists)
            return TRUE;   // an Intersect Exists
    }
    remove E from EQ;
}
return FALSE;      // No  Intersections

```

If one studies the C++ code provided at the bottom of the webpage, we see that this is simply a "next" and "previous" in a BST, however, I can't seem to tell which information is being used as the BST key.

My issue is the following: if we are considering all $y$-values at the current $x$-value of the sweep line, this is not merely a check for next or previous endpoint value in a BST, and can not take $O(\log n)$ time. However, if we are checking per endpoint coordinate, this could not possibly be correct, since the following situation would lead to an incorrect execution:

The algorithm should find that $B$ and $C$ intersection on insertion of $B$ into the search tree ("SweepLine" / "SL") while sweeping. However, if we are ordering by endpoint coordinates, $A$ is $B$'s previous, $C$ is not, and this would run into problems.

# Answer
> 2 votes
The BST is ordered with a "above/below" relationship. The idea is that for any "event", the BST is ordered by the y-value where each line segment intersects the x-value of that "event".

When a segment is inserted or deleted, the comparisons in the BST are between the y-value of each line segment *at the x-value of the current event*. This can be computed with geometry in constant time given the slope of each line. The ordering only requires a single update at each event (a little subtle); the BST requires no other maintenance.

In your example, at the 2nd event when C is added, it is actually inserted above A. Then the B/C intersection would be found correctly.

---
Tags: algorithms, algorithm-analysis
---


title: Universal One-Way Functions

text:
# Question
Title: Universal One-Way Functions
The Berman-Hartmanis conjecture discusses one-way functions (functions with hard to compute inverse functions).

As a step to solving the conjecture, if one-way functions could be reduced to a canonical or universal one-way function from which all one-way functions could be derived, this would be a major plus...

In a similar way, Turing devised a universal machine and Cook NP-completeness.

The question is then, are there universal one-way functions (discussed in the literature)? Can they be defined through NP-completeness?

# Answer
> 3 votes
That is an interesting question since there is no proof that one way functions exist. There is a lecture about this from Cornell's Cryptography course by Rafael Pass which can be found here

To summarize the lecture:

1. If one way functions exist then $P\neq NP$.
2. There exists a function $f\_{UNIV}$ such that if there exists any one-way function, then $f\_{UNIV}$ is a one-way function. Thus $f\_{UNIV}$ can be considered a universal one-way function.
3. $f\_{UNIV}$ works by acting on all Turing machines after $n^2$ steps of execution. It is defined as

$$f\_{UNIV}=M\_1^{(|x|^2)}(x)||M\_2^{(|x|^2)}(x)||\dots M\_{|x|}^{(|x|^2)}(x)$$

where $M\_{i}^{(|x|^2)}(x)$ denotes the output of Turing machine $M\_i$ on input $x$ right after $|x|^2$ steps of computation.
4. If a one way function $f$ exists it can be solved by a Turing machine $M$, which will be polynomial solvable by $f\_{UNIV}$.

Caution: the construction of $f\_{UNIV}$ is in no way practical. This is about asymptotic complexity, not practical security.

---
Tags: complexity-theory, one-way-functions
---


# Question
Title: Visualization of Lamport's three-dimensional "space-time diagram" with introduced "tick lines"
In the third page (the third paragraph in the right column) of the paper "Time, Clocks, and the Ordering of Events in a Distributed System" by Leslie Lamport, it says that

> The reader may find it helpful to visualize a two-dimensional spatial network of processes, which yields a three-dimensional space-time diagram. Processes and messages are still represented by lines, but tick lines become two-dimensional surfaces.

However I failed to visualize them in my head, especially the two-dimensional surfaces. Could anyone make more explanations? An illustrative picture would be excellent.

# Answer
Here's my take:

...and here's a 3D version without the nice colors.

Vertical black lines are processes; magenta lines are messages (wavy lines); spheres are events, and time is on the vertical (blue) axis. The planes are 'tick lines.'

In Dr. Lamport's original diagrams, messages are only passed between "adjacent" processes. Presumably in a real distributed system any process can send a message to any other process, but this is hard to draw clearly in a 2D diagram.
> 3 votes

---
Tags: distributed-systems, intuition, clocks
---


# Question
Title: Are there current benchmarks for algorithms solving Travelling Salesman?
I'm researching the travelling salesman problem and looking for data regarding the current state of affairs regarding solutions and performance. So far the only data I've states that the current record for optimality is held by 'Concorde' which found a solution for a graph containing 85,900 cities. I've also found benchmarking data for Concorde, as well as data pertaining to the current best performance for a world map.

Is this data still accurate? It looks like a lot of this hasn't been updated since the early 2000s.

# Answer
TSP has many variants under study eg Euclidean vs noneuclidean, exact vs approximations, interrelated but also at times separate threads of research. heres a recent nontechnical survey from early 2013 on TSP by an expert mathematical writer Klarreich, Computer Scientists Take Road Less Traveled that sheds some insight on recent improvements/ theoretical advances & can be mined for some refs. an old approximation algorithm by 1976 Christofides has been unrivalled for decades but some minor theoretical improvements have been made recently. as indicated in the article some theoretical TSP research that is not nec (practically) implemented veers into what is referred to as Galactic algorithm territory by expert RJ Lipton.

as a more applied resource/ angle, also a leading group/ site for benchmarking is DIMACS, NSF center for discrete math & CS, which also has a TSP page with algorithms/ benchmarks updated 2013.
> -1 votes

---
Tags: algorithms, reference-request, efficiency, traveling-salesman
---


title: Expressive power of lexer + parser

text:
# Question
Title: Expressive power of lexer + parser
Most modern compilers split their syntax analysis into a lexical phase that is followed by a parsing phase. The lexical phase is given by a regular expression, while parsing is guided by a context-free grammar.

What class of languages can be recognised this way? Context-free languages, or can we get into context-sensitive languages?

# Answer
As stated in the question, this recognizes only context-free languages.

Lexical analysis is actually a GSM mapping, i.e. a finite state transduction. Since CF languages are a full Abstract Family of Languages (full AFL), they are closed under inverse GSM mapping. Hence, if the sequences of lexemes parsed by the second phase belong to a context-free language, the original texts as a sequence of characters also belong to a context-free language. This 2 levels organization does not change the CF characters of syntax, assuming the second level is indeed context-free.

One point is worth noting, though it is a minor technical issue. To have this CF character of the second phase, it is necessary that identifiers be replaced by a finite set of standard categories represented each by a unique symbol. The same is true for literals such as strings or numbers. The point is that many languages do not in principle put any limit on the size of identifiers, or some literals, so that there is in principle an infinite number of them. But the context free grammar of the second phase must have a finite alphabet, like any CF grammar. Hence the lexical elements returned by the first phase cannot actually distinguish all identifiers, or all literals, for the second phase.

However the information is kept by other means for the more semantical phases of the compiling process.

It is true that any given program does have a finite number of identifiers and literals, but the point is that we are considering the language of all possible programs.

Another point is of course that texts of compiler accepted programs do not form a context free language as other constraints (such as declarations of identifiers) are imposed on programs, in parallel to the strictly syntaxic parsing process.

But, ignoring those more "semantics" constraints, some parsers also use a variety of parsing "tricks", such as prioritization of reduction rules to avoid ambiguities or non-determinism. As long as this is done with a finite memory and a pushdown stack that is used only within a fixed finite distance from its top, this does not get the syntax out of the context-free realm. However, what extra parsing rules may exist for the parser also have to be known to the users of the language, thus making the understanding of the syntax more complex to users, and giving more ground for misunderstanding. TANSTAAFL. Supposing this is used to reduce ambiguity, it could then happen that the user will read his program one way, while the parser reads it another way.

My own preference is for general CF parsers, that will detect ambiguity (which is, of course, decidable for a given string of an ambiguous language), and reject it as a programming error. But that is much a matter of taste in design.

Including the lexical phase into the context-free syntax may possibly make those extra rules more complex, as reasonning can no longer isolate lexical issues fron CF syntactic ones. It can also make the automaton underlysing the parser more complex, or call for more extra rules. Typically, if parsing the CF part of the syntax requires a lookahead that may include an identifier, the look-ahead becomes unbounded when identifiers are not reduced to one symbol by a lexical phase. Much depends also on the chosen parser generation technology.

Though there are some scannerless parsers used, I would think this applies more to languages with specific lexical and syntactic characteristics. But I am no expert on this, and the wikipedia page seems a bit weak on the general presentation side.

Finally, another interesting point, close to the initial question is error recovery. It is used by compilers so as to be able to catch many errors at each run, and was important when compiling was done in batch mode, rather than interactively. Many syntactic error recovery techniques are based on a formal model of finite state generation of errors, such as missing or extra symbol, or local garbling of the strings (this is also true for natural language processing). This can also be modeled by a GSM. Hence, ignoring again semantical aspects, the larger language of *programs with syntactic errors* accepted by a parser with error correction is also context-free.

*There is more in the comments, but how long should an answer be?*
> 4 votes

---
Tags: formal-languages, parsing
---


# Question
Title: Poly-time computability of inversion of poly-time real functions
At pp. 7-8 of Ker-I Ko's Computational Complexity of Real Functions (1991), the following is stated for one dimensional cases:

> Let $INV\_1$ be the operator that maps a one-to-one function $f:\[0,1\]\rightarrow \[0,1\]$ to its inverse function $f^{-1}$. Then $INV\_1(f)$ is polynomial-time computable for all polynomial-time computable, one-to-one real functions $f$ on $\[0,1\]$.

And for two dimensional cases:

> Let $INV\_2$ be the operator that maps a one-to-one function $f:\[0,1\]^2\rightarrow \[0,1\]^2$ to its inverse function $f^{-1}$. Then $P=NP$ implies that for all polynomial computable, one-to-one real functions $f$ on $\[0,1\]^2$, $INV\_2(f)$ is polynomial-time computable, and this in turn implies $P=UP$.

How is the one-dimensional case derived? And how can the two-dimensional case be extended to n-dimensions?

# Answer
> 2 votes
In 1-dimensional case, the function has to be strictly-monotone. Given $y\_n$ do a binary search to find $x\_n$.

If $\mathsf{P} = \mathsf{NP}$, given $y\_n$ we can guess $x\_n$ and then verify that $f(x\_n) = y\_n$. The dimension doesn't matter for this part.

For the other part, that is, if $INV\_d$ is polytime then $\mathsf{P} = \mathsf{UP}$, we can reduce it to $INV\_2$ by noting that every 2-dimensional function can be extended to a $d$-dimensional one by letting other coordinates map as identity. So for $d'\<d$, $INV\_d$ being polytime computable implies that $INV\_{d'}$ is also polytime. Therefore $INV\_d$ being polytime implies that $INV\_2$ is polytime and therefore $\mathsf{P}=\mathsf{UP}$.

---
Tags: complexity-theory, computable-analysis
---


# Question
Title: Pick a subgraph that maximizes the total cost of min-spanning tree among all subgraphs of the same size
There is a complete graph $G$ with $n$ vertices and each edge has a distinct weight.

Is there an efficient (not necessarily optimal) algorithm to select $k$ vertices from the graph $G$, such that the total cost of the min-spanning tree of the selected $k$ vertices will be highest?

In my case, $n$ is around 1000, and $k$ around 100.

# Answer
> 4 votes
Your problem is NP-complete, so you should not expect to find any efficient algorithm for it.

If we could solve your problem efficiently, we could solve the $k$-clique problem, too. Let $G$ be an unweighted, undirected graph; we are curious whether it has a $k$-clique. Translate it into an instance of your problem by making each edge have weight 2, and then for each pair of vertices $u,v$ that are not connected by an edge, add a new edge of weight 1. Now ask for the solution to your problem. Notice that there exists a way to select $k$ vertices such that the corresponding spanning tree has cost $2k$, if and only if $G$ has a $k$-clique (if $G$ does not have a $k$-clique, no matter how you select $k$ vertices, the cost of the spanning tree will always be $\le 2k-1$).

Since the $k$-clique problem is NP-complete, your problem is NP-complete, too. Therefore, we cannot expect an efficient solution for your problem, when $k$ is arbitrary.

# Answer
> 2 votes
A theoretically efficient algorithm can be obtained as follows for constant $k$. First, notice you can compute a maximum weight spanning tree by negating the edge weights and running Kruskal's algorithm. Then, observe there are $\Theta(n^k)$ ways to choose a set of $k$ vertices. We can step through each set, and compute a maximum weight spanning tree for each. The total run time will be $O(n^k m \log n)$, or even a little bit better by tuning Kruskal's algorithm with a disjoint-set data structure.

In practice, we can't live with the $n^k$ term when $k$ gets even moderately large. Since you don't require an exact solution, you could further apply heuristics into this. For example, to make $k$ smaller, first identify suitably many heaviest edges, and choose their endpoints. Then by some strategy, complete this graph to a spanning tree (say by trying all ways of picking the rest of the vertices).

Alternatively, you could consider a totally different approach. Take some good heuristic for finding a maximum weight $k$-clique, and then drop enough lightest edges to obtain a spanning tree. Or just a craft a more direct method yourself, I could imagine a genetic algorithm to be pretty good in your problem: pick random $k$-sets for your individuals, and as your fitness function you can use Kruskal's algorithm really.

By spending some more time thinking about this, you can probably find a faster exact algorithm too. I would start by following the idea in my second paragraph.

---
Tags: algorithms, graphs, optimization
---


# Question
Title: Optimal Algorithm for Finding Maximal Number of Colinear Points
Given a set of $n$ point in a plane, find the maximal number of colinear points (the points residing on the same straight line).

The crudest algorithm is to compute the slope and intercept of each pair of point, assuming infinite precision, find maximal number of appearance of the same pair of parameters.

Is there an algorithm more efficient (1) in the worst case, (2) on average? What is the optimal one (1) in the worst case which I suspect the crude method with complexity $n\choose 2$ is the optimal, (2) on average; and how to prove it?

# Answer
> 3 votes
**Algorithm:** RANSAC would be a good algorithm for this problem, if you think there exists a line such that a large fraction of points lie on that line. (However, if there is no such line, RANSAC is not a good choice.) In each iteration, it randomly selects two points, draws a line through them, and then checks how many other points fall onto that line. It then does many iterations repeatedly, and keeps the best line it has found so far.

**Analysis:** Suppose there exists a line $L$ such that a fraction $p$ of the points are on the line $L$. Then any particular iteration has a $p^2$ probability of picking two points on the line $L$ and discovering the line $L$. So, if you run RANSAC for $O(1/p^2)$ iterations, then with high probability the line $L$ will be detected. Each iteration takes $O(n)$ time, so the total running time will be $O(n/p^2)$. For some values of $p$, this will be faster than your crude algorithm (which has a $O(n^2)$ running time).

In short, the more points on the optimal line, the faster RANSAC will find it.

---

This doesn't answer your question about the best worst-case complexity. I don't know if it is possible to beat ${n \choose 2}$ worst-case complexity. I don't know if this is optimal or if there are better algorithms. Also, even in the case where we know there is a line containing many points and where we care about average-case complexity, I don't know if RANSAC is optimal or if one can do better.

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


# Question
Title: are there any decidable problems not verifiable in polynomial time?
As I understand it NP requires a solution to be verifiable in polynomial time. Can you provide examples of solvable problems not verifiable in polynomial time ?

# Answer
Given input $x = \langle M \rangle$, decide whether $M$ halts after $|x|!$ steps on input $x$.
> 5 votes

---
Tags: complexity-theory, computability
---


# Question
Title: Name for class of algorithms preserving accuracy/confidence
I am considering the following class of algorithms:

The algorithm has access to some probabilistic oracle (procedure) $f$ in addition to input.

The answer of procedure $f$ (we may assume it is boolean) may be incorrect with probability at most $p\<1/3$. The error of different calls to $f$ are independent (thus we may increase the confidence of the result by repeatedly calling $f$ with the same argument and taking majority).

The algorithm can call multiple times $f$ with any values.

We request that whatever the bound on error probability $p$ (unknown to the algorithm), the algorithm itselft must return its correct answer with error probability at most $p$.

**The question is: Is there any standard name for that class of 'confidence-preserving' algorithms?**

*For the sake of illustration, if we want to find the maximum of $3$ items and only have access to the items through some probabilistic oracle $f$ for comparing any pair of items, we can compare each pair $3$ times and take majority vote. The probability that each pair is ordered incorrectly is at most $3p^2$, hence the probability that we do not deduce the maximum correctly is at most $9p^2$. This is less than $p$ so the algorithm belongs to our class.*

# Answer
> 1 votes
I'm not familiar with any standard name for this type of algorithm. Go ahead and write your research paper and define a class with a name of your own choice (confidence-preserving seems like a quite good name to me).

---
Tags: algorithms, complexity-theory, terminology, randomized-algorithms
---


# Question
Title: Why are different logarithms in the same Θ even thought their difference diverges?
As I have read in book and also my prof taught me about the asymptotic notations

The general idea I got is,when finding asymptotic notation of one function w.r.t other we consider only for very large value of $n$.

So from here my confusion is-

$2^n=O(3^n)$ and $\log\_2 n=\Theta(\log\_3 n)$

First relation is clear to me and second relation is confusing me.Though I derived $\log\_2 n$ and $\log\_3 n$ to same base and noticed that $\log\_2 n=\log\_{10} n/\log\_{10} 2$ and $\log\_3 n=\log\_{10}n/\log\_{10}3$. So In both constant factor can be removed. So second relation is also OK.

Still there remain a doubt that when I see the graph plot of $\log\_2 n$ and $\log\_3 n$, $\log\_2 n$ is always above $\log\_3 n$ and grows faster than $log\_3 n$ i.e the difference of log values increases as n increases. Then I got more confused when I saw the graph plot of $x\_1=y$ and $x\_2=2y$ in which again $x\_2$ is above $x\_1$ and difference is increasing b/w them as $y$ increases.

So now I want to know .How do I distinguish from graph about the asymptotic relations of the function. In what sense they say one function is upper bounded by the other though 2 lines with different slopes also following this.Why don't we say one line is upper bounded by the other.We only say they are related by $\Theta$.

Please help me understand this concept.

# Answer
> 4 votes
You are missing one thing in your definition of asymptotic notation. In addition to only caring about large values of N, we also ignore constant multiplicative factors.

$f$ is $O(g)$ if there exists a large $N$ and a constant $c$ such that $f(x) \< c g(x)$ for all $x \ge N$

In the $\log\_3$ vs $\log\_2$ case its true that we have $\log\_3 x \< \log\_2 x$ for all big $x$. However, its also true that

$\begin{equation\*} \log\_2 x = \frac{\log\_3 x}{\log\_2 3} \end{equation\*}$

so we can choose some $c$ larger than $\log\_2 3$ to end up with:

$\begin{equation\*} \log\_2 x \< c \cdot \log\_3 x \end{equation\*}$

and thus $\log\_2 x$ is $O(\log\_3 x)$.

---

The same reasoning does not apply to $2^n$ and $3^n$. There is no constant multiplicative factor that will make the $2^n$ catch up to $3^n$ for all big $n$.

---
Tags: asymptotics, landau-notation
---


# Question
Title: Infer number of comets, based upon observations of their periodic visits to Earth
Can we algorithmically infer the number of comets that orbit the Earth, based upon periodic observations of them, if we cannot tell the comets apart? In more detail:

### The problem

* There is an unknown, fixed number of comets, `numComets` that pass by Earth and are visible from the ground.
* Each comet takes a fixed number of years to orbit Earth.
* Based only on this knowledge and the dates recorded that a comet was sighted in the night sky, determine `numComets`, **AND** determine the orbital period of each comet. You can use an unlimited amount of observation data (time), but the solution in the shortest amount of
time is preferable.

### Assumptions you can make

* All comets look identical from the ground; there is no way to visually identify them.
* No other object will be mistaken for a comet, and all comets will be seen.
* No comet takes more than 100 years to orbit Earth, and no new comets will be introduced.

As current answers have pointed out, the problem as it lay now is unsolvable. Would a solution be possible if `numComets` is known? (Even roughly get the right answer?) What modifications to the problem would have to be made otherwise, to still encasulate the spirit of the problem, and make it solvable? (or is it dead with no hope of solving accurately?)

### Further assumption

All comets start at a different point in their orbit. I.e. They do not all start their orbit at the same place like racehorses coming out of a gate.

### Clarification

Comets are only recorded once per year. So there is no difference between a comet that passes at the beginning of a year and at the end. The problem could just as easily have been worded as days.

# Answer
Based on the restriction you gave, that you cannot identify one comet from another, there is no difinative method of calculation. Here is a proposed situation, There are 2 comets following the same trajectory, they each orbit at exactly ten year orbit durations, so each one is seen every ten years, they are however exactly 5 years apart in their orbits. From the ground if we cannot differentiate between these two comets we only see a comet appear overhead regularly every 5 years, there is no way to tell if this is one comet appearing ever 5 years, or two comets appearing every ten years, but 5 years apart. From this it is impossible to deterministically say how many comets there are, so no algorithm can give you numComets with the assumptions that you have specified.
> 10 votes

# Answer
Observations begin with year 0.

Let $c\_{i,j}$ the number of comets sighted the first time on year $j$ that have an $i$ years orbit, with $i\in\[1,100\]$ and $j\in \[0,i-1\]$. Let $n\_k$ be the number of comets sighted on year $k$.

Each year of observation gives an equation: $$\sum\_{i=1}^{100}c\_{i,k\bmod i}=n\_k$$

The total number of comets is $$\sum\_{i=1}^{100}\sum\_{j=0}^{i-1}c\_{i,j}$$

There are $100\times 101/2=5050\\; $ variables, so one could think that this number of years of observation would give enough equations. But it is likely that many equations will turn out to be linear conbinations of others. On the other hand, this will be a system of linear Diophantine equations (i.e. using only integers). In this case, resolution may not require as many equations as there are variables.

To be sure to observe everything, it is better to do it until the set of comets return to its initial configuration, which is after a number of years that is the least common multiple of the first hundred integers: I have not computed it, but it seems to be somewhat longer than the current age of the universe (probably even when measured in seconds - it broke my LCM calculator). But as Tycho-Brahe taught us, astronomy is a science for the patient.

Maybe a better analysis would show that less years may be needed (I doubt it, but I am not sure). Else, we just get an approximation, or improve the precision of the solution as time goes by and more observations are available. Anyway, we know that there is some indeterminacy in the problem that prevents distinguishing an obit from its harmonics, as remarked in another answer. So we know we will not get enough linearly independent equations anyway.

Well, once we have the equations, we solve them as much as possible, and get a set of possible answers, depending on a few remaining variables that can be freely chosen.

Then we can impose a further constraint on the total number, which reduces by one the degree of freedom on the answer.

This is probably not be a complete resolution of the problem. Only integer solutions are acceptable, and it is not clear to me that resolving the equations give only integer answers.

Systems of linear equations are normally solved over a field, and integers do not form a field. So some of the solutions found will be rational numbers, as rationals do form a field. But that is not acceptable. Some integer solutions must exist, though, as it is an hypothesis of the question: parameters of the problem result from observation of a solution (except for the total number of comets which can only be given by an oracle). So integer solutions will have to be extracted from the set of rational solutions, I suppose with divisibility considerations.

But my memory of the properties of linear diophantines systems and their resolution is gone, whatever it was at an earlier age. So I leave this for someone else, unless I find enough information on the web, and the time to read it.

This calls for a few remarks.

* It is not a problem of algorithmics but of formalization.
* The OP obviously knew the solution before he asked

His strange behavior made me react. I am wary of technical questions supposedly naive, because the asker is often gone when I post the answer, not to come back ... and I hate it. Then the reaction of the OP gave me the clue: he knew. That was motivating.

I have an excuse: I am not a native speaker. What is the meaning of HCBP?
> 1 votes

# Answer
Let $t\_1, t\_2, ...$ be the times that comets were seen, in reverse chronological order (that is $t\_1$ is the latest).

Start with comet $t\_1$, and consider all *candidates* that were seen before. For example, if you assume that $t\_2$ is the same comet as $t\_1$, then the period is $T = t\_1 - t\_2$. Now all you need to do is to check whether there was a comet at times $t\_1 - 2T$, $t\_1 - 3T$, etc (depending on how rigorous you want to be). If not, then go to the next candidate ($t\_3$, and so on). If yes, then congratulations -- you established that comet $t\_1$ has period $T$. Exclude this comet together with all its previous sightings $t\_1 - kT$ from your dataset. If the dataset is not empty (not all comets have been identified yet), then start from the beginning.
> 0 votes

# Answer
there are many ways to interpret this problem eg as a machine learning problem. however there is some key theory that is relevant & deserves citing, that of the "N-body" problem in physics. this is the problem of predicting motions of objects based on relative gravitational attraction and its an old problem, long studied, and there is a large amount of theory on the subject. the theory originally developed in working to determine trajectories of planets in the solar system and dates at least to Newton. there are surprising new findings also such that there are instabilities and inherent chaotic dynamics to these types of equations. in other words predictability may be somewhat like the weather, namely that weather over the short term is moderately predictable but over the long term is not deterministically predictable (because of the so-called butterfly effect etc).
> -1 votes

---
Tags: algorithms
---


# Question
Title: If x operations cost O(x) amortized then how much xy operations cost?
True or False?

Say some data structure can perform $x$ operations in amortized $O(x)$ time. Then for a big enough $y$ it can perform $xy$ operations in worst case $O(xy)$ time.

My attempt:

$x$ operations in $O(x)$ amortized means $O(1)$ expected time for $1$ operation. Then for $xy$ operations it'd be $O(xy)$ amortized (and I think $O(x^2y)$ worst case). Therefore, the statement is incorrect.

But the answers sheet says i'm wrong. Why?

# Answer
> 2 votes
Amortized is not just probabilistic, it means that for some big enough $y$, $xy$ operations can't take a long time and will guaranteed to be $O(x)$ in average in worst case (and therefore $O(xy)$ for all $xy$ operations), even through some of operations may take even $O(xy)$ time itself.

https://stackoverflow.com/questions/200384/constant-amortized-time

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


title: Feasible solution existence

text:
# Question
Title: Feasible solution existence
I wonder what is the fastest way to check whether the intersection of a set of half-spaces is empty.

Right now I'm using a linear programming formulation (with Gurobi as solver) to check if there is any feasible solution to a linear program constrained with a lot of linear inequalities. Is it possible to perform the feasibility check without actually optimizing an objective function? I know that there are polynomial time optimization algorithms in O(n^3.5), but is it possible to reduce the time even more by skipping the linear optimization part?

In particular an iterative algorithm may be very beneficial for me, since I'm adding and removing inequalities to the system all the time and after each addition, I'm checking the feasibility again. Thus, the best would be a king of inductive approach which (using some previously collected information) quickly determines if the set stays feasible after addition of a new inequality.

I would prefer to write my own piece of code for this problem instead of using a 3rd party solver library.

I have seen a related post, but my question targets a general set of equations.

# Answer
## Theory

There's a simple argument to show you can't help to do *that* much better. In particular, testing for feasibility of a set of linear inequalities can't be *too* much easier than optimizing a linear objective function subject to a set of linear inequalities.

Why? If we want to optimize the objective function $\Psi$ subject to a set $\mathcal{S}$ of inequalities, one way to do that is to use binary search on the value of the objective function. This can be done by repeated feasibility testing of a set of linear inequalities of the form $\mathcal{S} \land \Psi \ge c$, where $c$ is a constant. In particular, you use binary search to find the largest value of $c$ such that $\mathcal{S} \land \Psi \ge c$ is feasible.

Very roughly speaking, binary search can be expected to succeed within $O(\lg n)$ iterations. Therefore, testing for feasibility can't be more than $O(\lg n)$ times faster than maximizing an objective function.

## Practice

I don't know of any more efficient way to test for feasibility of a set of linear inequalities, than simply to solve a linear program using standard linear solvers. Basically, you pick any old objective function, and use the linear solver to maximize it subject to the set of linear inequalities. I don't know of any procedure that is faster in practice than this straightforward approach.
> 0 votes

---
Tags: algorithms, computational-geometry, decision-problem, linear-programming
---


# Question
Title: Finding an element in a sorted array with at most three queries to larger elements
Given a sorted array **A**, we have to find the position of an element ***m*** in it. (It is also given that the element exists in the array.)

However there is a constraint. Like in a game you have **3** lives. If you probe any element ***x*** **\>** ***m*** in the array you will lose one life. You can probe as many elements you want which are smaller than ***m***. If you find ***m***, you win.

The solution to this should not be in linear time.

**What I tried:**

I will drop eggs from floors 1, 2, 4, 8.. And in **log n** time, I will find a sub-array in which ***m*** exists (at cost of 1 life). But this sub-array was of size at most **n/2**. I cannot repeatedly apply this process since, I have limited number of lives.

**My thoughts**

I am thinking that a solution does not exist to this problem which is faster than linear. How to prove this (if this is the case)? Can I create a contradiction from the assumption that a solution exists?

# Answer
If you have only one life only safe way is to check every element starting from minimal. It's $O(n)$

If you have two lives and limited with $k + 1$ comparisons the minimal element of array you can check first has index $k$, so we still have $k$ comparisons to check all previous elements one by one, if no lives was lost than next element to check has index $k + (k - 1)$ so total numbers of elements we can check is that way $n = k + (k-1) + (k-2) + ... + 1 = \frac{k(k+1)}{2}$ So if you have two lives you can find target element for ($k = \frac{1 + \sqrt{1 + 8n}}{2}$) $+1$ comparisons. It's $O(\sqrt n)$

So if we have three lives and $k + 2$ comparisons first we should check element of index $\frac{(k + 1)(k)}{2}$ than if we will lost life we will be able to check all earlier elements for $k + 1$ comparisons. So in full analogy $n = \frac{(k+1)(k)}{2} + \frac{(k)(k-1)}{2} + \frac{(k-1)(k-2)}{2} + \frac{(k-2)(k-3)}{2} +... + \frac{3\cdot2}{2} + \frac{2\cdot1}{2} = \frac{1}{6}(k+2)(k+1)(k)$

Therefore $n\> \frac{1}{6}(k)^3$ and $k \< \sqrt\[3\]{6n}$

So we can solve this for $O(\sqrt\[3\]{n})$

This is variation of quite known skyscraper and glass or crystal balls puzzle, though I may be didn't find correct name for it in English.
> 8 votes

---
Tags: algorithms, search-algorithms, search-problem, algorithm-design
---


# Question
Title: Is string matching and replacement considered in formal languages?
Is string matching and replacement, as an operation on strings or on formal languages, considered in formal languages?

1. For example, the family of regular languages, or the family of context free languages, ..., are closed under certain string operations.

I would wonder if these families or some others may be closed under string matching and replacement?
2. Are string matching and replacement equivalent to some combination of other string operations?
3. Or is matching and replacement considered in formal languages in some other ways?

Thanks and regards!

# Answer
Match & replace is a special case of rational transduction, a quite powerful class of string mappings with a number of nice properties.

The classes of regular, context-free and recursive enumerable languages are all closed against rational transduction (source), so this carries over to match & replace.

It does not seem as if the necessary elementary operations had a representation in formal language theory.
> 4 votes

# Answer
Well, basically the application of a production by a grammar *is* find & replace. So string matching and replacement is part of type-0 grammars, at the heart of formal languages. Iterated replacement is computing.

Or is that too simple?
> 3 votes

---
Tags: formal-languages, strings
---


# Question
Title: How can we design an efficient warehouse management program?
Assume that we want to develop a warehouse management system, which picks up plastic boxes and stacks them on a pallet. A pallet has a maximum of 5 vertical box stacks and the maximum height of a box stack is 1400 mm. There are 3 box sizes with varying heights (other dimensions are the same). The heights of the boxes are 170 mm, 200 mm and 270 mm. An item is possible to place only in one type of box. All boxes are compatible to stack with each other. There are only two objectives: the number of completed pallets should be minimal, and the height difference of towers of boxes can be at most 500 mm.

The goal is to design a warehouse management program, which takes the order as an input, that is, the information of ordered items and how many boxes has been ordered. The program should determine how many boxes of each product should be stacked on a determined pallet and on a specific stack. A single product is always associated with only one box type.

How should one construct this kind of a program? I'm looking for general design guidelines and the methods to achieve the desired result. All tips and advices are welcome. I appreciate your effort.

# Answer
> 1 votes
It looks like what you have is a variant of the knapsack problem. However, you have an advantage that, rather than trying to optimize one "sack", you're simply trying to minimize the number of sacks (or in this case, pallets.)

I would have my program start by adding up the total height of the boxes I have to stack, and dividing it by the total height I could get out of each pallet if I could pack it perfectly (in this case, 7000mm). If there's no possible way I could fit the boxes I'm given on less than three pallets, for example, I'm better off knowing that to begin with.

So once I've calculated my *P*, the number of pallets I *may* be able to fit my boxes on (if I'm lucky and calculate well) I'm going to start distributing my biggest boxes first. I've got 5\*P stacks to fill; I'm just going to go around them, always choosing the stack that's currently the lowest height to put the next box on. I'll continue that as I run out of the biggest boxes and move on to the next biggest.

If I'm fortunate, this is all I'll need to solve the problem. If I'm less fortunate, I'll have to have code that explores to see if swapping boxes around creates the room I need. This is where the problem gets hairy; there's only so much you can do other than just plain trial and error.

In planning for that contingency, I might be well-advised to do some searching to see if there are any "perfect" stacks that can be made with the box sizes I'll have to work with (for instance, 7 of the 200 mm boxes make a perfect stack). Any "perfect" stacks that I can make simplify the task of figuring out how to swap boxes between the remaining stacks ... or, regrettably, accepting that there's *no* way to swap boxes around so that they fit on our hoped-for number of pallets.

---
Tags: algorithms, packing
---


# Question
Title: What could 'two characters are terminals' mean?
In the context of this statement, what does 'a & b are terminals' mean?

> Stacks and queues can be used for determining whether a particular input string is in the language or not.
>
> L = {a^nb^m | m,n \>= 0, m \>= n, and a & b are terminals}
>
> Sample strings in L : abb, aabb, aabbb
>
> Sample strings NOT in L : aab, ba

# Answer
> 6 votes
It means that $a$ and $b$ cannot be further decomposed. For example we might consider the language $$ L\_1=\\{r^ns^m\mid n, m \ge 0, m\ge n, r\text{ and }s \text{ are 2-character strings over } \\{a, b\\}\\} $$ In this language, $r$ and $s$ could be any of $aa, ab, ba, bb$, so a string in $L\_1$ could be $bababbbbbb$, since with $r=ba, s=bb$ we could write it as $(ba)^2(bb)^3$. In effect, saying "$a$ is terminal" asserts that it's a character in the underlying alphabet.

The original definition of $L$ is reasonable, but rarely used in my experience. An equivalent statement would be $$ L=\\{w\in \\{a, b\\}^\*\mid w=a^nb^m, n, m\ge 0, m\ge n\\} $$ or the alphabet $\\{a, b\\}$ would be inferred from context and usually wouldn't be stated. On any of my students' work, I'd accept $$ L=\\{a^nb^m\mid n, m\ge 0,m\ge n\\} $$

---
Tags: formal-languages, terminology
---


# Question
Title: Check if an array is a substring of another array
Given two sequences $A$ and $B$, we want to check if $A$ is a subsequence of $B$ where the elements of $A$ appear in $B$ consecutively and in the same order.

Example 1.

* input: $A = (4 , 6 , -5), B = (2 , 4 , 6 , -5 , 4)$,
* output: Yes

Example 2.

* input: $A = (2 , 6 , 4), B = (2 , 4 , 6 , -5 , 3)$,
* output: No — although $B$ contains all the elements in $A$, the order is not correct.

Example 3.

* input: $A = (2 , 6 , 4), B = (2 , 3 , 6 , -5 , 4)$,
* output: No — although $B$ contains all the elements of $A$ in the correct order, they are not consecutive.

Let $n$ and $m$ be the size of $A$ and $B$.

## How fast can we solve this problem?

## What I have tried

I have an algorithm that runs in time $O(nm)$ as follows:

> go over elements of A, for each of them go over elements of B and see if we can find a matching element, which is after the matching element for the previous element of A.

# Answer
> 5 votes
The problem is called **substring search** or string search or string matching. It's called a substring even if the elements of the array aren't characters. In this answer, I'll use *character* to refer to elements of the arrays, but this can be any kind of data (numbers, nested data structures, …). The standard terminology is:

* **subset** (without multiplicity): all the elements of $A$ are also found in $B$. For example $(1,2,3,1)$ is a subset of $(3,4,1,2)$.
* **subset with multiplicity**: for every element of $A$, there is a corresponding element in $B$. The difference from the basic subset problem is that if an element in $A$ is repeated, it must be repeated at least as many times in $B$. For example $(1,2,3,1)$ is a subset of $(3,4,1,1,2)$ but not of $(3,4,1,2)$. The terminology around this problem isn't completely standardized, sometimes ”subset“ refers to this.
* **subsequence**: the elements of $A$ are also present in $B$, in the same order, but there may be other elements in between. For example $(1,2,3)$ is a subsequence of $(0,1,0,2,3,4)$ and $(1,2,2,3)$ but not of $(3,1,2,0)$.
* **substring**: the elements of $A$ are also present in $B$, in the same order and consecutively. For example $(1,2,3)$ is a substring of $(0,1,2,3,4)$ but not of $(1,2,2,3)$.

Substring search is a very well-studied problem. The naive approach, where you take each possible starting position in $B$ in turn and try to match $A$ there, runs in $O(m\\,n)$ where $m$ is the length of $A$ and $n$ is the length of $B$.

The naive approach can be improved because it often ends up making tests which could have been known to be false or whose outcome doesn't affect the final result. For example:

* If one of the elements of $A$ never occurs in $B$, this can be noticed with a single pass in $B$, in time $O(n)$: there's no need to test the other characters of $A$. More generally, if a character in $A$ occurs rarely in $B$, it's best to match this one first against the elements of $B$.
* When matching `abcdabe` at the start of `abcdefabcdabcdabe`, once position $5$ is reached (`a``e`), the naive algorithm tries to match $A$ starting at position $2$. An improvement is to notice that the first character of $A$ wasn't present in the positions of $B$ that have already been read, so there's no need to test $A$ again against earlier positions.

Improved substring search algorithms rely on preprocessing $A$ to notice opportunities like these to make the matching more efficient. For example, a simple approach from a theoretical perspective is to build a deterministic finite automaton that recognizes the regular expression $\mathord{.}^\*A$, which recognizes all strings that end in $A$. If the automaton ever reaches an accepting state, this indicates that $A$ has been found as a substring of $B$. This algorithm requires a preprocessing phase on $A$ which requires $O(m^2)$ time; after this, $B$ can be processed with no backtracking. Each position in $B$ requires $O(1)$ time to analyze the character in $B$ and look it up in the table of transitions from the current node in the automaton. Thus the running time for the search (including preprocessing) is $O(m^2 + n)$.

Two common substring algorithms are:

* Knuth-Morris-Pratt, which builds on the same idea as the finite automaton, but constructs a more specialized table in time $O(m)$, for a total running time of $O(n)$.
* Boyer-Moore, which also builds a table, and tries matching from the end of $A$, which allows it to skip characters in $B$. The basic Boyer-Moore algorithm has a $\Theta(m\\,n)$ worst case (like naive search), but can pass over non-matching strings in time $n/m$ in the best case. There are Boyer-Moore variants with an $O(m+n)$ worst case.

Intuitively, $O(m+n)$ is as good as it gets, since in the worst case all characters in $m$ and $n$ must be read (the worst case being reached when $B$ is full of substrings that are close to $A$ but not identical).

# Answer
> 1 votes
The problem can be solved in time $O(m+n)$ (check the algorithm for *longest common subsequence*).

We have to read all elements of $A$ and $B$ in the worst case, so it cannot be solved faster than $\Omega(m+n)$.

---
Tags: algorithms, algorithm-analysis, substrings
---


# Question
Title: What is the maximum directly adddressable memory capacity?
This is taken from *OPERATING SYSTEMS: INTERNALS AND DESIGN PRINCIPLES by WILLIAM STALLINGS*

Consider a 32-bit microprocessor composed of 2 fields: the first byte contains the opcode and remainder an immediate operand or an operand address. What is the maximum directly addressable memory capacity?

Now the answer should be `2^24=16777216 bits = 2 megabytes` but the solution set says `2^24=16 MBytes`

So am I wrong or is the solution set wrong?

# Answer
Start with a simpler example. Suppose you only had 3 address bits, rather than 24. With $3$ bits we could have $2^3=8$ addresses: 000, 001, 010, 011, 100, 101, 110, 111. In this case, we could think of memory as being divided up into 8 chunks, of equal sizes, with one address per chunk:

```
memory:  chunk 0 | chunk 1 | chunk 2 | chunk 3 | chunk 4 | chunk 5 | chunk 6 | chunk 7
address:   000       001       010       011       100       101       110       111

```

For example, the contents of chunk 3 would be addressed by the three bits 011. Now how much memory would there be in total? It'll clearly be 8 times the size of a chunk. Stalling is using a memory model where the chunks are bytes, so with 3-bit addresses, we would have a total memory of $2^3=8$ bytes: one byte per address.

A different computer, though, might be built so that each chunk was 4 bytes. On such a machine with 3-bit addresses we would have $8\times 4 = 32$ bytes of memory, 4 bytes per address.

At any rate, with 24-bit addresses, we'd have $2^{24}= 16777216 = 16\text{M}$ possible addresses, hence that many possible chunks. If each chunk was a byte that would mean that the total addressable memory would be 16777216 bytes, or 16MB. Similarly, if each chunk was 4 bytes long, the total addressable memory would be (chunk size $\times$ number of addresses), or $4\text{B}\times 16\text{M} =64\text{MB}$.
> 5 votes

# Answer
Most modern processors do not address memory at the granularity of single bits but limit the size of the smallest chunk of memory that can be accessed to an 8-bit byte. This is called byte-addressable memory.

With byte-addressable memory, a 24-bit immediate could directly address any of 224 *bytes*, i.e., 16 MiB.

Stallings is assuming byte-addressing, so 224 *bytes* would be directly addressable.

---

In the past, some processors used word-addressable memory, where the smallest chunk that could be accessed was equal to the size of the registers. By using a larger smallest chunk size, fewer bits were needed to address a given size of memory. E.g., with a 32-bit word size, a 24-bit immediate would be able to reference 224\*4 bytes (64 MiB). (Using word-addressable memory also simplified memory access.)

Outside of some DSPs and embedded systems processors, word-addressable memory is not very popular today.

As a side note, some microcontrollers have special mechanisms for atomic bit addressing such bit-band regions (e.g., ARM), where a section of the address space is bit-addressable, and atomic set and atomic clear bit instructions (e.g., MIPS), where three bits of the instruction specify the bit within a byte.)

It might also be noted that some ISAs shift immediate values by the access size (e.g., accessing a 2-byte value would shift the immediate by one bit). This assumes that the base pointer and the address of the value are properly aligned, i.e., that the least bit is zero for a 2-byte value, the two least significant bits are zero for a 4-byte value, etc. This allows a smaller immediate to provide a larger access range when accessing values larger than a byte.
> 3 votes

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


# Question
Title: counting arithmetic progressions $a, a+r, a+2r$ in a list
I have a large list $L$ of numbers and I need to count instances of elements $a,b,c \in L$ such that $a +c = 2b$. A brute-force approach would be to check all possible triples $(a,b,c)$ and this will run in $L^3$ time.

Can I do any better?

# Answer
> 3 votes
Given that the OP is rather unprecise as to the kind of numbers he is considering (though he later said integers or integers modulo $p$ in a comment), I will try to answer nevertheless, by trying to limit the number of assumptions I can make. And while I am at it anyway, I will generalize a bit.

*This builds on the contributions of previous answer and comments, by Rick Decker, Hendrik Jan. and HEKTO.*

**Generalized statement of the problem**

We consider four sets of values $\mathcal{U}, \mathcal{V}, \mathcal{W}, \mathcal{Z}$, two functions $f:\mathcal{U}\times \mathcal{V}\to \mathcal{Z}$ and $g:\mathcal{W}\to\mathcal{Z}$. Given 3 sets or lists of values $U,V,W$, respectively from $\mathcal{U}, \mathcal{V}, \mathcal{W}$, count the number of triples $(u,v,w)\in U\times V\times W$ such that $f(u,v)=g(w)$. Each computation of the functions $f$ and $g$ is supposed to be in constant time.

Let $n=max(|U|,|V|,|W|)$

**General solution**

*This is essentially HEKTO's suggestion.*

Build a hash table containing each value $w\in W$ indexed by $g(w)$. This has a cost $O(n)$ under the Simple Uniform Hashing Assumption(SUHA). Without the SUHA, one can use a balanced tree with complexity $O(n\log n)$.

Then for each $u\in U$ and for each $v\in V$ check whether $f(u,v)$ is in the hash table in constant time (or in the balanced tree in logarithmic time). If it is in an entry $g(w)$, then add $(u,v,w)$ to the list of solutions (or increase the solution count by one).

Complexity is $O(n^2)$ with hash table, under SUHA, or $O(n^2\log n)$ with a balanced tree.

**Case of ordered sets**

*This is essentially Hendrik Jan's suggestion.*

We assume that one of the two sets $\mathcal{U}$ or $\mathcal{V}$ (say $\mathcal{V}$, w.l.o.g.) and the set $\mathcal{Z}$ are totally ordered and that the function $f$ is monotonic with respect to the argument in the ordered set (here the second argument).

Then we can have a modified algorithm that does not need a hash table.

First sort the set $V$.

Build a list $L$ of pairs $(w,g(w))$ for all $w\in W$, sorted with respect to the second element.

Then for each $u\in U$, compare the ordered values of $f(u,v)$ with the ordered values $g(w)$ of the pairs in $L$, by moving up the two list $V$ and $L$ as you would do for set intersection, and add the answer $(u,v,w)$ whenever $f(u,v)=g(w)$ for some pair $(w,g(w))$.

Complexity is $O(n^2)$.

**Application to "numbers" and arithmetic progression**

We consider the initial problem of detecting arithmetic progressions in the elements of a list.

The three lists of the abstract case are the same list. The function $f$ is addition, and the function $g$ is doubling (i.e. product by 2).

The ordered set solution applies well to integers, rationals, or reals (with some care).

Complex numbers are not an ordered field. However they can be considered as an ordered groups with respect to addition, by prioritizing coordinates, so that $a+ib\> a'+ib'$ iff $a\>a' \vee (a=a' \wedge b\>b')$. So the ordered set construction can be used.

The hash table algorithm seems necessary in the case of $\mathbb{Z}/p$ (i.e. integers modulo $P$) since non-trivial linearly ordered groups are necessarily infinite, which is not the case for $\mathbb{Z}/p$.

However the ordered set construction could be adapted to $\mathbb{Z}/p$ without loss in complexity, by allowing the list $L$ to be scanned twice, with some proper bookkeeping.

# Answer
> 2 votes
An often-useful technique is to sort the list first. Then, starting with the smallest element, $x\_1$, consider pairing $x\_1$ with $x\_2$. For them to be the first two terms in an arithmetic sequence, you'll need to have an $x\_i = (x\_2-x\_1)+x\_2$. You can find such an element by, say, a binary search. If that fails, look at the pair $x\_1, x\_3$ and do the same thing. Once you've exhausted the pairs starting at $x\_1$, look at the pairs $x\_2, x\_3$, then $x\_2, x\_4$ and continue, counting the successes.

The sorting will take $O(n\log n)$ steps. You'll have to check $O(n^2)$ pairs and for each do a binary search for the third element, for a total of $O(n\log n+n^2\log n)$ steps.

There are some improvements you can make to this algorithm, but this should get you started.

# Answer
> 2 votes
Sort the list increasingly, in time $O(n\log(n))$.

For every $j$, consider the two sequences formed by the left-differences $L\[j\]-L\[j-1\], L\[j\]-L\[j-2\],L\[j\]-L\[j-3\]...$ and the right-differences $L\[j+1\]-L\[j\],L\[j+2\]-L\[j\],L\[j+3\]-L\[j\]...$

By a simple list merging process, you will detect all equal values in the two lists, corresponding to arithmetic triples, using no more than $\min(j,n-j)$ comparisons.

Repeating for all $j$, you count all arithmetic triples in time $\Theta(n^2)$.

```
# Input (presorted)
L= [ 1, 2, 3, 6, 7, 9, 11 ]; n= len(L)

# Try all middle elements
for j in range(1, n - 1):
    # Detect all arithmetic triples by merging the left and right lists
    i= j - 1; k= j + 1
    while 0 <= i and k < n:
        if L[j] - L[i] < L[k] - L[j]:
            # Advance in the left list
            i-= 1
        elif L[j] - L[i] > L[k] - L[j]:
            # Advance in the right list
            k+= 1
        else:
            # Report a triple and advance in both lists
            print L[i], L[j], L[k]; i-= 1; k+= 1

```

Output:

```
1 2 3
3 6 9
1 6 11
3 7 11
7 9 11

```

This is worst-case optimal, as a perfect arithmetic sequence has $\Omega(n^2)$ arithmetic triples. Constant extra space.

A much harder challenge is to find an output-sensitive solution (when the number of arithmetic triples is $o(n^2)$).

---
Tags: algorithms, number-theory, lists
---


title: Semantic Code Comparison

text:
# Question
Title: Semantic Code Comparison
Consider two codes that do the same thing, in the same time and memory order, But they don't do it exactly the same way. Is there any Idea for a program to declare those codes as the same?

For Example:

**Change Vars 1**

```
a = a + b;
b = a - b;
a = b - a;

```

**Change Vars 2**

```
int temp = a;
a = b;
b = temp;

```

or consider two bubble sort codes that sort ascending, one starting from the end, one from the beginning of the array.

There is the idea to execute both codes and then check if the memory status is similar after the execution of both codes. But that's not very comprehensive.

Edit: My focus is on Turing complete languages mostly.

# Answer
> 3 votes
I have two news for you. I start with the bad one.

## The dark side of the question

Computation theory tells us that checking whether two programs, or program fragments, are equivalent is not decidable.

What that means is only that there is no unique technique that can check that equivalence of any pair of programs. This remains true if you consider a single programming language, as long as it is Turing complete. (Note: I do not understand what you intend when mentionning Turing complete algorithms in your comment - and, by the way, *precisions should be integrated in the question, preferably to comments*).

No unique technique also means no unique finite set of techniques as they could be applied simultaneously. It also means no infinite set of techniques that is finitely describable, etc.

This can be formally proved on Turing machine with Rice theorem (which is a bit subtle to use). The proof can be tediously transposed to any other Turing complete formalisation of computation. But invoking Church-Turing thesis is usually considered enough.

To summarize it, there is no way you can produce a system that will take two arbitrary program fragments of a Turing Complete language and tell you when they are equivalent semantically, i.e. when their computation results are the same.

But do not despair, there is hope.

## The bright side of the question

While the above is true when you make the question so general, it does not mean that this can never be done. Actually, this, or problems very close to it, is the object of considerable reasearch. The undecidability statement should only be seen as a limitation to what is to be expected, but there is considerable room within that limitation.

So, there are many situation when it is actually possible to apply a procedure that will actually decide whether two (fragments of) programs are actually equivalent. The applicability of such a procedure can be defined by a language (that is not Turing complete), or by some limitation on the computational power such fragments can express (so that they do not have to be in the same language).

Much of the research related to type theory also concerns provability of programs properties, and can lead to answers to your question. But that is much outside my competence.

Many other techniques have been developed for your purpose.

## About your examples

Your idea of running both codes and comparing results is a good one, at least in simple cases, like your example.

But you have to run the code symbolically, and then use a symbolic computation system to check that the answers are indeed the same.

So, assume that initially a==$a$ and b==$b$, where I use italics for symbolic expressions, i.e. non evaluated formulae. The symbols $a$ and $b$ just stand for themselves, and have no associated value.

**running the first code:**

a = a + b; - - so a==$a+b$
b = a - b; - - so b==$(a+b)-b$
a = a - b; - - so a==$(a+b)-((a+b)-b)$

Recall, again, that what is in italics is just symbolic expressions, trees if you prefer. There is nothing to be computed.

**running the second code:**

int temp = a; - - so temp==$a$
a = b; - - so a==$b$
b = temp;; - - so b==$a$

Now you give these results to a symbolic calculator that check that the values of variables a and b are the same at the end. It must be able to simplify expressions such as $(a+b)-b$ and $(a+b)-((a+b)-b)$ to respectively $a$ and $b$, which requires using known algebraic properties of the operators $+$ and $-$.

It is actually a good technique (when applied properly - I goofed my first try),as it allowed me to notice that your two codes were not equivalent, and I corrected the first one.

Running the code symbolically is an example of a general paradigm called abstract interpretation. The "casting out nines" test is a very elementary example of these techniques.

Symbolic evaluation and abstract interpretations are a well studied way of proving things about programs.

It is pretty much what is done by type checkers.

But it is far from the whole story about proving things about programs. Large systems are being developed to prove properties of programs by different means.

In other cases (probably for your sorting examples), it may be better to have a specification of what the program is supposed to do and separately prove the two pieces of code conformant with that specification. This avoid having to consider simultaneously the specifics of two algorithms.

---
Tags: terminology, semantics
---


# Question
Title: Partially homomorphic encryption (on addition modulo N) not based on prime factorization
A cryptographic function is homomorphic on some operation if that operation is preserved in the encrypted data.

Such a function is homomorphic on addition modulo if the following holds for some cryptographic function $E$:

$ E(x)\cdot E(y) = E(x+y\mod N) $

and on xor:

$ E(x)\cdot E(y) = E(x \oplus y) $

This is called a partially homomorphic encryption.

Such schemes are described on the Wikipedia page:

http://en.wikipedia.org/wiki/Homomorphic\_encryption

However, all the partially homomorphic schemes on XOR and addition modulo are based on prime factorization.

Are there partially homomorphic encryption methods on XOR or addition modulo that do not are not based on prime factorization (other than the fully homomorphic system proposed by Gentry based on lattice cryptography).

This paper by Mykletun, Girao and Westhoff suggests the El-Gamal method:

http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=99E3442A4CF314F9AF334969DF9C7974?doi=10.1.1.61.5322&rep=rep1&type=pdf

# Answer
> 5 votes
Typical ElGamal is homomorphic with respect to multiplication. You can get an additively-homomorphic variant by encrypting $g^m$ instead of $m$. When you decrypt, however, you will get back $g^m$, not $m$. Therefore, you have to solve a discrete log to get $m$ back. This is feasible if we place certain restrictions on $m$ (e.g., the space from which $m$ is drawn is small enough to brute-force the discrete log). Security of ElGamal relates to solving discrete logs.

You can get an elliptic curve variant of ElGamal by using an elliptic curve group instead of a multiplicative group of integers modulo some number. This will get you an additively homomorphic cipher without the need to solve discrete logs. Security of this cipher would relate to solving discrete logs in the elliptic curve group.

I am not aware of alternatives for XOR.

---
Tags: cryptography
---


# Question
Title: Algorithm to partially sort list into equal-sized buckets
Suppose I have a large list of numbers that I want to divide into equal-sized buckets so that every bucket contains only larger numbers than buckets to its left. Numbers within each bucket don't need to be sorted.

For example, for the input

```
[64, 72, 57, 47, 5, 4, 64, 21, 64, 65, 36, 43, 81, 44, 19, 87, 17, 86,
 73, 21, 19, 64, 94, 91, 34, 49, 8, 52, 18, 37]

```

that I want to divide into 5 buckets, some valid outputs would be

```
[[4, 5, 8, 17, 18], [19, 19, 21, 21, 34], [36, 37, 43, 44, 47],
 [49, 52, 57, 64, 64], [64, 64, 65, 72, 73]]

[[8, 17, 18, 5, 4], [21, 19, 21, 34, 19], [43, 37, 44, 36, 47],
 [52, 57, 49, 64, 64], [64, 64, 72, 73, 65]]

[[8, 18, 5, 4, 17], [19, 19, 21, 21, 34], [47, 36, 44, 43, 37],
 [52, 64, 49, 64, 57], [64, 72, 64, 65, 73]]

[[18, 8, 17, 5, 4], [21, 19, 21, 19, 34], [36, 44, 43, 37, 47],
 [57, 64, 64, 49, 52], [64, 72, 64, 65, 73]]

```

One approach to do this would be to sort the list, and then divide it at equal intervals. Can this be done faster?

I would also be happy with a result where the buckets are of only roughly equal size, but note that I can't assume a uniform distribution for the numbers, so bucket sort doesn't help.

# Answer
Assuming you want to create $k$ buckets, to the following.

1. Obtain elements of rank $\lceil n/k \rceil, 2 \cdot \lceil n/k \rceil \dots, (k-1) \cdot \lceil n/k \rceil$.
2. Perform multi-way partitioning (cf. Quicksort) with these elements as pivot.

Both steps take time $\Theta(kn)$. All buckets are within $\pm 1$ of the same size.

In the case of duplicate elements, you can "uniquify" them in a $\Theta(n)$ preprocessing run; otherwise bucket sizes might differ more.

Essentially, this is performing only the top-level call of a $k$-way Quicksort with perfect pivots. All variants regarding pivot selection and partitioning apply and will lead to different runtime and bucket size characteristics.
> 4 votes

# Answer
Just thought of this off the top of my head. You could try to use a B+ tree, with number of pointers $m=k$, where $k$ is your bucket size.

The leaves would be your partitioned buckets. If you went from the list to the B+ tree, then each insert is $O(log\_k(n))$ and for n items, it would take $O(n\*log\_k(n))$ for inserting the entire list. If you are using a B+ tree you happen to have direct access to the B+ structure, you could just collect the pointer to the leaf nodes.

You could also just get rid of the list altogether sacrificing a $O(1)$ insertion to have the buckets already created for you in the B+ tree in $O(1)$.

One down side, is that the buckets may not be full, but they will be partially ordered.
> 0 votes

---
Tags: algorithms, sorting
---


title: Reduction to Maximum Independent Set

text:
# Question
Title: Reduction to Maximum Independent Set
Suppose you had a set $P$ of people. Every person $p\_j \in P$ is familiar with atleast one other person $p\_i$ (familiarity is symmetric). Is there a subset $S$ of people such that for $|S| \ge k$, no two people in $S$ know each other? Show that the problem is NP-Complete.

Clearly this resembles the Maximum Independent Set problem, however, I am having trouble seeing how to do the reduction. My idea is to generate a graph $G'$ such that vertices represents people and an edge between two vertices means those two people know each other.

The problem is, this graph can be disconnected so any ideas as to how this can be reduced?

**EDIT:**

Take for instance this graph $G'$

One possible Maximum Independent Set is clearly $\\{2,3,7,5\\}$ but does it matter if the graph is disconnected?

# Answer
> 4 votes
Your problem, as stated, is already the independent set problem, as defined e.g. on Wikipedia.
A very similar NP-Complete problem is Clique, which is part of Karp's original 21 NP-complete problems, where, given a graph $G$ and an integer $k$, you try to find a complete subgraph of size $k$. It is easy to see that looking for an independent set in a graph is the same as looking for a clique in its complement graph.
In Karp's paper one can also find a straightforward reduction from SAT to Clique, and the reduction does not depend on whether the graph is connected or not. Hence it does not matter whether your graph is connected or disconnected.

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


# Question
Title: What is a sort in programming language semantics?
In Chapter 1 of *Practical Foundations for Programming Languages*, the author mentions that abstract syntax trees are associated with *sorts*.

Intuitively, sorts are like types, but I'd like to know if they have a precise definition. I'd be glad if some references are provided as well.

# Answer
It depends on what semantics we would take for types and sorts. -- However a brief - little informal - definitions could be - *Sorts are classes of ASTs and types are classes of values*.
> 4 votes

# Answer
There is actually much similarity between sorts for the abstact syntax and types as usually understood. But **sorts are a formal syntactic concept**, and AS trees are syntax too, while **types are a semantic concept**.

The terminology comes from term algebras (also called *free algebras*) and universal algebra. These are essentially syntactic theories of algebraic structures, analyzed independently of any interpretations. They were developed in the first half of the 20th century.

A term may be seen as a tree, where the nodes are labeled from a finite set of operators, each operator having a fixed arity that specifies the number of daughters in the tree. Arity 0 is for leaves. In *multi-sorted algebras* this is refined with sorts, so that each operator belong to a sort, and arities are replaced by an ordered list of sorts, that fixes for each daughter the sort of its head operator. The sort of an operator, together with the list of the sorts of its daughter, is called the *signature* of the operator.

In universal algebras, this is further refined by introducing equationally defined equivalence relations between terms.

Though it seems to have faded a bit, these concepts were quite popular and much studied in computer science in the late 20th century, as abstract algebras where then seen as a basis for abstract data types, which is, in part, precursor of what is nos classes in object oriented programming.

Universal algebras are related to the development of category theory, which is also foundational in current vision of types and programming languages.

Algebras are syntactic object, and are intended to be used with an interpretation in some semantic domain(s) corresponding to types. **An interpretation is a homomorphism that maps sorts into domains of values (types)**, and operators into functions between those domains, so that signatures are respected, and equations too in the case of an equational algebra. This is how you can apply the results of group theory to any domain with an operation that respect the definition of a group.

This organization was considered very convenient by early researchers in programming languages, especially those concerned with formalizing programming languages. It had the advantage of isolating syntax and semantics, and of being mathematically well understood.

Another reason for adopting it was a concern with the development of tool to manipulate programs, either in development environments or in formal systems to prove properties of programs (which turned out to be more and more twin problems).

This lead to the emergence of the concept of *abstract syntax tree (AST)* for programming languages, which are essentially terms of a multi-sorted algebra (sometimes refined with a use of sort union in some sytems). The AST is the reference syntax for a language, from which semantics can be defined by homomorphism as in denotational semantics.

Not only is this convenient to study semantics of languages, but trees are better structured thans strings and thus a better basis for developing programming tools and programming environments.

It allows to isolate parsing which was traditionnally a messy part as the limitations of parsing technology forced the use of distorted grammars. It also factors out presentation issues.

It allows for multiple concrete (string or graphic) representations of programs, which can sometimes be convenient (there is no reason why using punctuation rather than tabs, or the converse, in program syntax should be forced on people).

It makes it easy to define **many interpretations of programs, and of sorts**, in order to analyze program properies with abstract interpretations.

It is convenient for writing (semi-)automated program manipulation tools, for example for automatic program transformations, or translations between languages.

Things may sometimes be a bit more complicated in practice, because some forms of Abstract Syntax allow some operators to buid trees (expressions) that belong to several sorts (an informal way to look at it). For example there could be a sort for syntactic constructs that represent variables (assignable entities), and another for expressions. But any variable can be used as an expression, the converse being false.

Early papers on this, for programming languages, date back to the mid-seventies. The conceptualization at the time was intended for the production of syntax conscious (the word "directed" was then used) programming environments. Look for Mentor and Centaur in Europe and for Cornell Program Synthesizer in the USA. They were the first two system to actually use such concepts in a practical way. Many others were developped afterwards.

But abstract syntax predates these systems. The Lisp language (1958) had abstract syntax, which is no surprise as it was developed by a logician, and for the purpose of making programs that manipulate programs (see also ML and LCF ... that came later). But Lisp was not sorted : everything was syntactically a list and more refined structure was essentially semantics dependent. This lead some people to consider, somewhat incorrectly, that Lisp had no syntax.
> 4 votes

# Answer
It appears in chapter four that sorts are for syntax and types are for semantics.

The example syntax chart on page 40 deals with the sorts in the language L{num str}. Apparently sorts are categories in the syntax of the language.

In particular, "plus" has a sort, which is the syntactic category of its result. The sort of the operator "plus" is named "Exp". That represents the fact that syntactically, an invocation of the operator "plus" is an expression. An invocation of the operator "plus" can fill a position in an abstract syntax tree where an expression is permitted. That's what kind of construction a "plus" is. That's how it fits into the structure of a text that represents a program.

The type system on page 41 deals with the types in language L{num str}. The type of operator "plus", given that its operands have type "num", is "num". This judgment is a partial description of the semantics of operator "plus". That is, part of the meaning of the operator "plus" is the combining of two numbers to produce a number. This meaning distinguishes "plus" from other expressions.

Furthermore, there is a sort named "Typ" that contains the two types, "num" and "str".
> 2 votes

# Answer
In the beginning of Chapter 1, Harper gives a hint as to what he means by the word *sort*:

> The syntax of a language specifies the means by which various **sorts of phrases** ***(expressions, commands, declarations, and so forth)*** may be combined to form programs.

He defines the word *phrase* as an abstract syntax tree, which he then discusses.
> 1 votes

---
Tags: terminology, programming-languages, semantics
---


title: Proof technique in complexity theory

text:
# Question
Title: Proof technique in complexity theory
I have a (stupid ?) question about complexity theory. It's about a "proof technique".

I want to compare 2 models of computation. I want to prove that for each langage recognized in polynomial time by a machine of the first model, there exists a machine of the second class that recognizes the same langage in polynomial time. Can I use this argument in my proof :

> Let M be a machine of the first class that recognizes a langage L in time T(n) (where T is a polynomial, and n the size of the input word). Let N be a machine of the second class that is able to computes T(n) ...

The idea is to use the knowledge of T(n) to have a bound on the space used on each input by the machine of the first class, which that makes the construction of the machine of the second class easier. However, it seems a bit strange to say that we explicitly know T(n)... Is it allowed ?

# Answer
> 3 votes
You can indeed assume that you know a polynomial bound on the time it takes to compute a polytime function. This is an example of a non-constructive argument.

The down side is that you won't be able to construct a *computable* function transforming polytime function of one model to the other. In some situations (say a diagonal argument) this is needed, and then the trick is to assume that programs are *clocked*, i.e. come with their own time bounds. This makes sense in that application since we can enumerate all polytime functions as computed by polynomially clocked machines. In your case, however, you don't need to worry about such issues.

---
Tags: complexity-theory, proof-techniques, simulation
---


# Question
Title: How, in hardware, MIPS can access a word in the middle of an address
This is am example of a RAM address in the MIPS architecture (32 bits)

I can imagine the RAM as having 32 pins just to inform the RAM address I want to access, so I can access each of these words in the image (because I saw in this vídeo). I think, then, it should need another 32 pins to inform what's the word in that address, just like in the vídeo. I don't know, however, how the CPU could support 2 different 32 pins bus (but this is another problem).

What I don't understand, for real, is why I need and offset in the instruction "load word", if I can only access one address at the time! What if I say "load word", give the address number 2, and then say na offset of 4? It will load part of the word from the address 2, and part from the address 3? How is this possible?

# Answer
> 4 votes
First of all, to short circuit your question, I must say that you can not ready from multiple memory locations at the same time in the MIPS architecture.

Second, your interpretation of the offset is wrong. You assumed the offset is a bit offset, while it's actually an offset in bytes. Meaning if you give the address 2 and offset 4, the memory location to be read from will be 6 (2+4).

Third, more details into the MIPS lw (load word) instruction. The syntax is as follow: lw \\$d, off(\\$r), where \\$d is the destination register (where the word is loaded to), off is an immediate 32 bit constant and \\$r is your base register. What happens is as follow:

1. The target ram address is calculated by adding off and the value in \\$r.
2. The calculated address in loaded in the memory register
3. The control unit enabled the RAM to get the value at the address
4. The value is set to the \\$d register

Fourth, something I haven't mentioned before, related to the addressing pattern of the ram. As you may know, the ram stores bytes, no actual words. What's the problem you may wonder? It's something called word alignment, and it's the reason why you couldn't load a word from address 6. A word is a 4 byte value, and for fast design purposes, when loading a word, the address has to be a multiple of 4. I won't go in the design details, but suffice to say that this permits greater memory transfer speed than allowing any address.

What this means is that when loading and storing words, you have to respect the word boundaries. If you try to read from a bad memory location i.e. not a multiple of 4, e.g. 6, you will have a memory exception; meaning you program likely crashes.

In practice, this mean that if you have to store tree words a,b and c, you could store them at address 0x01234560, 0x01234564 and 0x01234568.

**EXTRA: why use an offset**

So, in my last example, you might have noticed my words were close in memory, but i didn't start at 0x00000000. Actually, the first word starts at adress 0x01234560. Here's how you can take that into consideration with the lw syntax.

1. First, set the value of \\$r to 0x01234560
2. Then, to load a, you write lw \\$d, 0(\\$r). The will load the value at 0+\\$r, 0 + 0x01234560 = 0x01234560
3. Then, to load b, you write lw \\$d, 4(\\$r). The will load the value at 4+\\$r, 4 + 0x01234560 = 0x01234564
4. Then, to load c, you write lw \\$d, 8(\\$r). The will load the value at 8+\\$r, 8 + 0x01234560 = 0x01234568

I hope this completely answers your question. The only thing I haven't touched is why you'd end up at such complex memory locations. Short answer: it's due to the structure of the compiled program and the way it's loaded into memory. I suggest you look further into that before delving deeper into the world of computer electronics. A sound knowledge of the structure of a program will greatly help understand why the CPU and instruction set were made that way.

---
Tags: computer-architecture, memory-management
---


title: Recursive equations vs. inference rules

text:
# Question
Title: Recursive equations vs. inference rules
It seems to me that recursive equations can always be presented as inference rules. For the forward direction, an example is addition over Peono numerals (built from $O$ and $S(\\\_)$)

$$ \begin{align} add(O, m) & = m \\ add(S(n), m) & = S(add(n, m)) \end{align} $$

which can be also presented as

$$ \frac{ }{add(O, m) = m} \qquad \frac{add(n, m) = a}{add(S(n), m) = S(a)} $$

Is the backward conversion (from inference rules to recursive equations) always possible? If not, it seems inference rules more general, right? Except the superficial difference between the presentations, is there any other deeper difference between the two?

# Answer
Inference rules are "more general". A recursive equation, actually any equation $E\_1 = E\_2$ is like an inference rule without premisses: $$\frac{}{E\_1 = E\_2}$$ A general inference rule may have premisses, and so it is like a *conditional* equation. Only very special kinds of inference rules may be equivalently expressed as equations. For instance, it seems difficult to express $$\frac{a \bullet c = b \bullet c}{a = b}$$ and $$\frac{add(x,add(y,z)) = add(x,z)}{add(y,z) = z}$$ as equations.
> 3 votes

# Answer
I think recursion is more fundamental than inference rules. Note that I mentioned recursion and not recursive equation.

Recursion can be defined as a property of definition of some concept where the definition uses/include/refer to the concept itself that was being described. Now this concept can be anything or can have any particular representation. It could be inference rules, equations, relations, functions etc. From this point of view recursions is more fundamental than inference rules or any other notations of concepts.

**UPDATE**

To be more precise as par the question, yes it is possible to convert a inference rule to recursive equation if the inference rule is recursive.
> 0 votes

---
Tags: logic, recursion
---


# Question
Title: Mininun changes required in a directed graph to make path from 1 to n
i have a directed graph. Basically, i have to find how many edges i need to change to opposite direction to make a path between 1 and n. So, i tried solving it by making the graph undirected and marking the directions as -1 or +1 and then going through all paths and finding which paths has minimum -1(s). I store graph data in adjacency list (because number of edges can be large) and perform dfs. I also stop travelling a path if its count of -1(s) is more than the previous minimum. I also stored in every element the previous count of -1(s) to reach it from start. and i stop if current count is more. If less, i update it and move on this path and update if the new count is minimum. But this approach is slow. What else can i try?

# Answer
> 2 votes
Construct a weighted directed graph as follows. For each edge (u,v), there are an edge (u,v) of weight 0 and an edge (v,u) of weight one. Then, there is an path from 1 to n of weight k iff we can change direction of k edges to make a path. Thus, the problem can be solved by a shortest path algorithm. Since the edge weights are either 0 or 1, it can also be solved by BFS.

---
Tags: algorithms, graphs, dynamic-programming, graph-algorithms
---


# Question
Title: Difference between memory access and write-back in RISC pipeline
I'm a little confused about the difference of the memory access and the write-back stage in a `RISC pipeline`.

We learned in class these following assumptions:

```
arithmetic & logic: IF, OF, EX, WB
load: IF, OF, EX, MA, WB
store: IF, OF, EX, MA
branch: IF, OF, EX

IF=Instruction Fetch, OF=Operand Fetch, EX=Execution, MA=Memory Access, WB=Write-Back

```

Lets say we have the following code now:
`I1: LD R1, 0(R2) ; load R1 from address 0 + R2`
`I2: ADD R1, R1, #1 ; R1 = R1 + 1`
`I3: ST 0(R2), R1 ; Store R1 at address 0 + R2`

According to what I've learned `I1` will pass all five stages, `I2` won't have to access the memory, and `I3` won't have a write-back.

But then I wonder, how and where does `I3` store the value then? Just in the memory? And `I2` fetches the value from memory, but needs to write-back to some place other than the memory? So does that mean that write-back is always to the HDD?

I think I'm missing some core concepts here, as to where the operand is fetched from and where it gets stored to.

# Answer
In a classic 5-stage RISC pipeline, WB writes a value into a register. If the instruction doesn't write a value into a register (e.g. store), then that stage isn't used.

I1 stores a result into a register (namely R1), so it uses WB.

I2 stores a result into a register (R1) so it uses WB.

I3 does not store a result into a register, so it doesn't use WB.

You basically got it with I3: the store instruction stores to memory, so the "write" is performed inside MA.

Incidentally, on "real" RISC machines, MA tends to be more complex (and multi-cycle) because of multi-level caches and virtual memory. A store instruction may cause a page fault, so in a sense it has a "result" that isn't just the memory access.
> 9 votes

# Answer
I did not quite understand your question I am trying to answer.You can ask further if it is not clear.As we know in RISC machine most of the instruction will be performed on registers and memory is addressed only in index mode.I1 will store value in memory address given by R2.I2 will not access memory as it has all sources and destinations as registers.And write back stage is only used for register read and write.
> 0 votes

# Answer
There are also cases a store will have a writeback. For example store-conditional which will return status when accessing a memory location.
> 0 votes

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


# Question
Title: How can we combine badly trained decision trees to a good one?
I was reading about decision trees and this is what I understood:

We build decision trees by choosing an attribute and building subtrees (which are also decision trees) as children of the node representing that attribute. This means that as we go down, in building a decision tree, the no. of training instances that we use to build a subtree decreases. This is because when we build a subtree, we only have to train it using a subset of the original data consisting of instances which satisfy the conditions on the path towards the root node of the subtree.

Now here's the question: We usually believe that if training data is not enough, the model built is incorrect. This would mean that the subtrees down in a decision tree may not be good models (as they were trained using much less data than its ancestors in the tree) and if they are not, how can they be recursively combined to give a full tree which may give a good model? Where is the fault in my reasoning?

# Answer
Your question is a good one and note that in the extreme case, if every leaf node contains only one data point then you are almost certainly over-fitting and/or missing the "true" dimensions that separate the two points above. One way around this problem is to not split at a node (make it a leaf) if it contains fewer than C points, where C is something like 10. Also, a decision tree in the Brieman/Cutler framework uses $\sqrt{N}$ randomly chosen dimensions to try to split on, at a node with N points. Thus you are somewhat avoiding over-fitting because of this (but it's random so it's not very reassuring). The best solution is to create many (like 100 or more) bootstrap replicates of your data and build a decision tree for each bootstrap replicate. Then for prediction, you run the point through all 100 trees and take the average of the prediction indicator vectors to get predicted class probabilities. You can take the highest probability to be the predicted class. This strategy is much more robust to over-fitting because splits with low data support in one tree will only appear in the majority of trees (either exactly or approximately) if they have higher overall data support.
> 1 votes

---
Tags: machine-learning
---