# Question
Title: Help Understanding the Type and Complexity of my Programming Task
I'm working on a programming task that I, without good evidence, have a sneaking suspicion is NP-Complete. With that said, I would like confirmation on this if possible, as well as some suggestion for a way to approximate a reasonable solution. Lastly, if this problem is just some popular problem in disguise, I'd love to look more into that problem. I'll now describe my task.

I am attempting to design a program to optimize daily fantasy baseball rosters given certain information. The context here is that I will be designing rosters of players from various games that consists of 2 pitchers and one player that plays each other position. This is complicated by the fact that each player is assigned a salary relative to their perceived ability and there is an overall cap on how much salary can be used in total. This means I am dealing with restrictions in terms of making sure that I do not exceed the combined salary cap, while also making sure that I have players at each position. To complicate things further, I want to be able to pick a few players (1-5 or so) at each position as my favorites, and have control over what % of my teams they appear in. That is, if I make 50 teams, I'd like to be able to make it so that I can generate these teams by inputting a list like: Player X (pitcher) 5%, Player Y (First Base) 50%, and so on.

Is there any practical way I can solve (approximate fairly accurately) this problem? The overall salary limit seems to make this a tricky problem.

Thanks a lot!

# Answer
Divide this problem into two parts.

> I am attempting to design a program to optimize daily fantasy baseball rosters given certain information. The context here is that I will be designing rosters of players from various games that consists of 2 pitchers and one player that plays each other position. This is complicated by the fact that each player is assigned a salary relative to their perceived ability and there is an overall cap on how much salary can be used in total. This means I am dealing with restrictions in terms of making sure that I do not exceed the combined salary cap, while also making sure that I have players at each position.

This sounds like the 0-1 Knapsack problem where you have an overall salary cap and salary and importance of each player.

So from a list of all the players available in the market, form your personal roster using this concept.

Now coming to the second part of your question,

> I want to be able to pick a few players (1-5 or so) at each position as my favorites, and have control over what % of my teams they appear in. That is, if I make 50 teams, I'd like to be able to make it so that I can generate these teams by inputting a list like: Player X (pitcher) 5%, Player Y (First Base) 50%, and so on.

You have a personal roster at hand and each player has a percentage attached to him. Try a greedy strategy to distribute players.

Pardon my ignorance of baseball's rules but here is a simple example to help you out. Suppose you have 10 teams where each team has to have only one keeper (the guy who stands behind the players with the bats). You have to distribute Keeper X, Y and Z among the two teams. X has a 10% percentage chance, Y has a 90% chance, Z has a 10% chance. So sort the players according in ascending order according to weightage and put X in team 1, Y in team 2 and Z in teams 3 through 10. Similarly sort according to your criteria, and develop your own heuristic to fill each position.
> 1 votes

---
Tags: time-complexity, np-complete, optimization, constraint-programming
---


# Question
Title: Does the Rabin-Karp really need me to care about applying a mod Q operation on the rolling hashes?
I have been reading about the Rabin Karp algorithm and I kept wondering what's the big deal with keeping our rolling hashes values bounded by a value Q?

I'd thought that as our integer number representation on the typical computer is 2-complement, it's actually exactly equivalent as bounding all our operations over the rolling hashes by 2^31, so that in other words, I simply shouldn't care. Plus, the smaller we bound or hashes to, the more collisions we'd have, so a bigger Q should equal with improved performance!

I've tried coding a simple (Java) implementation:

```
public static int rabinKarp(String text, String pattern) {
    if (text.length() < pattern.length()) {
        return -1;
    } else {
        int patternHash = 0;
        int textHash = 0;
        int pow = 1;

        // preprocessing the pattern and the first characters of the text string
        for (int i = pattern.length()-1; i >= 0; --i) {
            patternHash += pattern.charAt(i) * pow;
            textHash += text.charAt(i) * pow;
            pow *= 10;
        }
        pow /= 10;

        // actual search
        if (patternHash == textHash && areEqual(text, 0, pattern)) {
            return 0;
        } else {
            for (int i = 1; i < text.length()-pattern.length()+1; ++i) {
                textHash -= text.charAt(i-1)*pow;
                textHash *= 10;
                textHash += text.charAt(i+pattern.length()-1);
                if (textHash == patternHash && areEqual(text, i, pattern)) {
                    return i;
                }
            }
            return -1;
        }
    }
}

```

From some preliminary tests, my hypothesis seems to be empirically accurate, yet I have not seen that written anywhere, so I am left wondering..

Am I missing something?

# Answer
> 11 votes
Yes, in practice you can get by fine with just letting the computations overflow. You are effectively working modulo $2^{32}$. It also has the advantage of not requiring an (expensive) modulo computation. However, it lacks some of the theoretical performance guarantees. You need to be very careful with the choice of the base (in this case: $10$) with respect to the modulus.

In particular, your choice of $10$ is very poor. Note that $10^{32}=2^{32}\cdot 5^{32}$, so $10^{32} \textrm{ mod } 2^{32} = 0$. This means that only the last $32$ characters of the string are taken in to account in the hash, so one can construct an input on which your algorithm performs very poorly.

Let the haystack be a string of $m$ $1$'s, i.e. $1111111\ldots$ and the needle a string consisting of $n$ $1$'s, one $0$, and then $32$ $1$'s. Because the string ends with $32$ $1$'s every position will result in a spurious hit, and the algorithm will need to loop over $n$ $1$'s before encountering a zero, meaning you will get a $\Omega(nm)$ running time.

I tested your algorithm on an input where $n=3000,m=n^2=9\cdot 10^6$. It took $18$ seconds to run on an input that ended in $32$ 1's, but only $200ms$ for a string ending in $31$ $1$'s.

The problem is that $10$ is not relatively prime to the modulus. For instance, taking $9$ as the base makes your program perform much better, taking only $200ms$ for the case with $32$ $1$'s. Of course, taking a prime modulus will partially solve this problem since the base will automatically be relatively prime to it. However, this is not the only reason for preferring a prime modulus.

Now, even if the modulus $n$ and base $b$ are relatively prime, undesirable things can still happen. For instance, there is a $k$ for which $b^k=1\textrm{ mod } n$. It is undesirable for $k$ to be small, since the hash function can not distinguish every $i^\textrm{th}$ character from every $i+k^\textrm{th}$ character. In mathematical terms you want the order of $b$ mod $n$ to be as large as possible.

The order of $b$ mod $n$ is always at most the Euler-Phi function $\phi(n)$. For a prime $p$, $\phi(p)=p-1$ while for non-primes $n$ it will be smaller. So taking $n$ to be a prime will allow more of the values of $b^k$ to be "useful". Ideally, one should take $b$ to be a primitive root modulo $n$, making that $b^k=1 \textrm{ mod } n$ does not hold for any value of $0\<k\<\phi(n)$.

Note that you can always construct instances for which the performance is poor, and to protect against "attacks" from an adversary you need to take the base and modulus to be random values.

---
Tags: algorithms, strings, rolling-hash
---


# Question
Title: Showing that the pumping lemma cannot prove that some language is not regular
I have this language $ L = a^\* \cup \left \\{ a^mb^n|m\>n\geq 0 \right \\}^\* $ I have to prove that this language is not regular but still satisfies the pumping lemma for regular languages (Since the pumping lemma is a necessary but not sufficient condition for a language to be regular). First I made the leap that $L$ is equivalent to $L' = \left \\{ a^mb^n|m\>n\geq 0 \right \\}^\*$ since this language already contains $a^\*$(I hope it's correct). My question is: to prove that the pumping lemma holds is sufficient to prove that exists a word in this language that satisfies the lemma or that must hold for all words in the language? For example in this case we could consider the word $aaa$ it's easy to say how this word satisfies the pumping lemma because $aa^ia \in L' \space \forall i \geq 0$.
This means that proving the pumping lemma holds for a language is easy (must find an instance in whitch it holds) but proving it doesn't hold is harder (must prove that it doesn't hold for all instances of the language).

# Answer
> 5 votes
The idea of this exercise is to show that the pumping lemma is not a sure-fire method to prove that a language isn't regular. To show that, we need to come up with a language that (i) isn't regular, but (ii) cannot be proved not regular using the pumping lemma. This is the goal of your exercise.

The "pumping lemma method" for proving that a language $L$ isn't regular is a sort of game:

* The adversary gives you an integer $p$.
* You come up with a word $w \in L$ of length at least $p$.
* The adversary partitions the word into $w = xyz$, where $|xy| \leq p$ and $|y| \geq 1$.
* You come up with an integer $i$ such that $xy^iz \notin L$.

If you win this game then you have shown that $L$ is not regular. In order to show that the pumping lemma cannot be used to prove that $L$ is regular, you have to show that the adversary wins the game.

A winning strategy for you is, for each $p$, a word $w \in L$ of length at least $p$, and for each legal partition $w = xyz$, an integer $i$ such that $xy^i z \notin L$. This is how you apply the pumping lemma. A winning strategy for the adversary is an integer $p$ such that *each* word $w \in L$ of length at least $p$ can be legally partitioned as $w = xyz$ in such a way that $xy^i z \in L$ for all $i \geq 0$. This is your goal in this exercise.

If the pumping lemma doesn't work, what does work? There is a generalization of the pumping lemma in which you mark $p$ locations of the word $w$, and then the adversarial partition $w = xyz$ must satisfy (i) $xy$ contains at most $p$ marked locations, (ii) $y$ must contain at least one marked location. Sometimes this generalized version works when the usual one fails, but not always.

One method which is guaranteed to always work is the Myhill–Nerode criterion. If a language is not regular, you can always prove it (in principle) using the Myhill–Nerode theorem. In many cases it is also easier to apply than the pumping lemma, even when the latter does work. What pity that it is beyond the curricula of many courses!

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


# Question
Title: Eliminate non-local references from closure
For a code similarity detection framework I need to eliminate references to non-local variables, for example having the following closure:

```
{
  var a;
  var b;

  var f = function() {
    a = 5;
    b = 6;
  }

  f();
}

```

would be converted into something like:

```
{
  var a;
  var b;

  var f = function() {
    var a = 5;
    var b = 6;
    return tuple(a, b);
  }

  a, b = f();
}

```

Another approach would be:

```
{
  var world;
  var a;
  var b;

  var f = function(world) {
    world = update_world(world, "a", 5);
    world = update_world(world, "b", 6);
    return world;
  }

  world = f(world);
  a = get_world(world, "a");
  b = get_world(world, "b");
}

```

Basically, convert a stateful program to a purely functional one. The goal is then to transform the resulting program into the lambda calculus, normalize and look for isomorphic subtrees.

Is there a formalization of what I'm trying to do?

# Answer
## Denotational Semantics was an answer almost intended for your question

*There is a huge collection of techniques that may be applicable, since the proposed task is basically a compilation process, possibly partial / incremental compilation. The target language is domain extended λ-calculus, which imply some standard transformations such as continuations or passing state as parameter and (part of) result of functions. So it can be described by piecemeal compiler and functional programming bibliography.*

*But the systematic view of compiling programming languages to λ-calculus is precisely one of the purposes of defining denotational semantics of programming languages, though it is a consequence of the original aim: defining a compositional semantics. Compositionality is precisely what is naturally given by λ-calculus. This is illustrated by the fact that the first environment for building systematically the denotational semantics of a language, P. Mosses'SIS, was also considered the first complete compiler-compiler.*

*Denotational semantics offers a systematic framework for the stated goal, with a strong and fairly unified theoretical basis.*

> Basically, convert a stateful program to a purely functional one. The goal is then to transform the resulting program into the lambda calculus, normalize and look for isomorphic subtrees.
>
> Is there a formalization of what I'm trying to do?

**Yes, there is a formalization of what you are trying to do**, and it has been existing for 35 years, though some techniques may have evolved, It was for example applied to the very imperative language Ada around 1980.

What you want is very precisely and formally what is done by using **denotational semantics**: transform your stateful program, or program fragment, into a lambda expression. It does use many compiling and functional programming techniques, such as continuations and other higher order functions.

Indeed the structure of the last example in the question, introducing a memory environment called `world` is typical of denotational semantics. In denotational semantics `world` is a "state mapping" $S:\mathrm{State}$ representing the memory state. This state is passed as argument to all functions, so that functions can access global memory (by whatever means), and returned by function to be available in the calling environment. Of course the $\mathrm{State}$ value returned may differ from the one received as parameter, exactly as the `world` value returned by function `f` is not the one it received.

For some simple examples, you may look at the question: Denotational semantics of expressions with side effects.

If you have a reference denotational semantics for the language you are considering, then you are sure that no language feature is forgotten in the translation process that could invalidate what you are trying to do.

If you do it on an ad hoc basis for a specific program fragment, you get no garantee that you are taking all you should into consideration.

If you do not have a denotational semantics definitions for your language, you may get ideas from looking at how it handles specific features for other existing languages., or look at the denotational semantics literature in general.

I know denotational semantics does not seem very popular these days. But it was developed and used for that purpose, in addition to more theoretical and abstract aims.

*The idea of thus using denotational semantics was pionneered by Peter Mosses with his Semantics Implementation System (SIS)1* developed in the late 1970s. It was doing just that: transform (compile) programs into big lambda expressions according to the denotational semantics of the programming language, which had first to be entered in the system.

There is considerable literature and books on denotational semantics, which you can easily find by searching the web.

Not surprisingly, many of the techniques used are compiler writing techniques, and the system SIS is considered as the first compiler-compiler. Hence much of the literature on compilers can be relevant too, as shown by the important bibliography in the previous answer by Wandering Logic.

The fact is that **a denotational semantics specification of a programming language can be read as high-level code for a compiler of the language into lambda calculus**, up to some predefined domains of values.

1 Peter Mosses, "SIS: A Compiler-Generator System Using Denotational Semantics," Report 78-4-3, Dept. of Computer Science, University of Aarhus, Denmark, June 1978
> 1 votes

# Answer
I think what you want is essentially conversion to static single assignment (SSA) form, followed by *closure conversion*, followed by conversion to *continuation passing style*.

*Static* single assignment form guarantees that each variable is written exactly once in the program text. That this is the key step in converting imperative to functional programs is argued by

> Andrew W. Appel. SSA is functional programming. *SIGPLAN Notices*, 33(4), 1998.
>
> Richard A. Kelsey. A correspondence between continuation passing style and static single assignment form. *Proc ACM SIGPLAN Workshop on Intermediate Representations*, January 1995.
>
> Peter J. Landin. The mechanical evaluation of expressions. *Computer Journal*, 6(4):308–320, 1964.

This starts to get really interesting for programs with loops. You need to convert the loops into recursive calls, and make a unique copy for the variables written in each iteration of the loop. In the traditional loop optimization community this technique is called *scalar expansion* or (sometimes) *dynamic renaming*.

> David J. Kuck, R. H. Kuhn, David A. Padua, B. Leasure, and Michael Wolfe. Dependence graphs and compiler optimizations. In Conference Record of the Eighth Annual ACM Symposium on Principles of Programming Languages, pages 207–218, Williamsburg, VA, January 1981.
>
> Ron Cytron and Jeanne Ferrante. What’s in a name? The value of renaming for parallelism detection and storage allocation. In Proceedings of the 16th Annual International Conference on Parallel Processing, pages 19–27, St. Charles, IL, August 1987.

In the functional programming community this involves making closures and continuations explicit:

> Andrew W. Appel and Trevor Jim. Continuation passing, closure-passing style. *Proc. Symp. on Principles of Programming Languages (POPL)*, 1989.
>
> Guy Lewis Steele. RABBIT: A compiler for Scheme. Technical Report AITR-474, MIT Artificial Intelligence Laboratory, May 1978.

I needed to do these conversions, for the automatic parallelization techniques described in my dissertation. Chapters 3, and 9.1.

> Matthew Frank, SUDS: Automatic Parallelization for Raw Processors, Ph.D. thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, May 23, 2003.
> 7 votes

---
Tags: reference-request, programming-languages, compilers, functional-programming, imperative-programming
---


# Question
Title: What is the global function we are trying to Optimise with Clustering Algorithms?
I am doing some reading (and implementation) of some Clustering Algorithms.

First I started with the well known K-Mean algorithm and implemented it directly from a paper. Got a kind of decent understanding of what I going on there.

What I am actually interested in is Particle Swarm Optimisation based clustering.

For Particle Swarm Optimisation, you need to have a global fitness function that will (in this case) tell you how well clusters this is.

The general notion of well clustered I have found is that *each cluster is compact*. But how to express this mathematically?

I thought that we would go though each cluster and check its positional variance (away from its centroid).

For some cluster C :

$$\mu(C)=\dfrac{1}{|C|}\sum\_{\forall\tilde{x}\in C}\tilde{x}$$

$$\sigma^{2}(C)=\sum\_{\forall\tilde{x}\in C}\left(\tilde{x}-\mu(C)\right)^{2}$$

No point converting to standard deviation, unless using a gradient based optimization approach, which PSO is not.

then the global fitness would be to minimize the average variance, which is proportional to minimizing the total variance since we have a fixed number of clusters.

if $S$ is the set of all clusters the we are to minimise some function $g$.

$g\_{mine}(S)=\sum\_{\forall C\in S}\sigma^{2}(C)$

ie $$g\_{mine}(S)=\sum\_{\forall C\in S}\sum\_{\forall\tilde{x}\in C}\left(\tilde{x}-\mu(C)\right)^{2}$$

---

According to *Chen, C.-Y. & Ye, F. Particle swarm optimization algorithm and its application to clustering analysis Networking, Sensing and Control, 2004 IEEE International Conference on, 2004, 2, 789-794*

Equation 7 (Rewritten to use my notation)

$$g\_{chen}(S)=\sum\_{\forall C\in S}\sum\_{\forall\tilde{x}\in X}(\tilde{x}-\mu(C)) $$

The difference from what I had is the $\forall\tilde{x}\in X$, for $X$ the whole spaceof data rather than $\forall\tilde{x}\in C$.

This is what got me wondering if I was correct in the first place. as it can be seen that $g\_{mine}\ne g\_{chen}$. It can't since the extra points are going to change it and will not cancel since all variances are positive. However they are equivalent if $\forall S, S'$ $g\_{mine}(S)\ge g\_{mine}(S') \iff g\_{chen}(S)\ge g\_{chen}(S')$

---

In: *Ahmadyfard, A. & Modares, H. Combining PSO and k-means to enhance data clustering Telecommunications, 2008. IST 2008. International Symposium on, 2008, 688-691*

Equation 6 has: (again with notation switched)

$$g\_{ahmadfard}(S)=\dfrac{1}{|X|} \sum\_{\forall C\in S}\sum\_{\forall\tilde{x}\in C}\left(\tilde{x}-\mu(C)\right)^{2}$$

This is equivalent to mine (at least in proportionality) as: $|X| \times g\_{ahmadfard}(S) = g\_{mine}$, and since $|X|\>0$ thus $\forall S, S'$ $g\_{mine}(S)\ge g\_{mine}(S') \iff g\_{ahmadfard}(S)\ge g\_{ahmadfard}(S')$

---

Ye and Chen also came up with another function in: *Ye, Fun, and Ching-Yi Chen. "Alternative KPSO-clustering algorithm." Tamkang Journal of science and Engineering 8.2 (2005): 165.* It is very complicated and beyond the scope of this question

---

* **What are the pros and cons of $g\_{chen}$ vs $g\_{mine}$ vs $g\_{ahmadfard}$ ?**

# Answer
> 3 votes
About your first, general question: generally, the cost function we want to optimize in clustering algorithms is double: we want to **both minimize intra-class variance while maximizing extra-class variance**. Replace class by cluster and you understand easily what it means: inside a cluster, we want the elements to be as similar as possible, while elements between different clusters must be as dissimilar as possible. The basic idea is very simple and natural.

Different algorithms will only tweak the way they measure this intra-class similarity and the extra-class dissimilarity, usually in the goal to optimize for a particular kind of dataset with known properties.

About the second, more specific question: I did not read those papers, but from a first look, it seems gchen is using L1-norm (absolute value measure) while gmine is using L2-norm (euclidian measure). gahmadfard seems to only be the L2-norm plus feature scaling or some kind of tf-idf (anyway what is certain is that they are pondering the similarity measure with the number of elements in the group, but I don't know for what purpose).

I can't advise when to use which clustering algorithm, you should read the intro of the papers or find a survey, but **usually the best way to find the best clustering algorithm for you is to try several on your dataset and manually select which one fits the best your purpose** (since there's no objective way to find which clustering is the best, it all depends on your subjective needs, after all, clustering algorithms belong to the class of unsupervised learning).

---
Tags: optimization, cluster
---


# Question
Title: Complexity of finding these original parameters
I am given (or rather, generate randomly) three positive integers $a, b, c$. I want to know if there exist integers $m \ge 2, s \ge 1$ such that $ms+m = a, ms+1 = b, 2s+1 = c$. If there are multiple solutions, I want the minimal (if possible).

It is clear that $c$ has to be odd, so if $c$ given to me is not, then I can immediately stop the computation. However, I'm not sure what other cases there can be.

Also, I'm not sure if there is a better alternative than the following (or even brute-force): let $d = \min(a, b, c)$, and have $m, s$ be roughly $\sqrt{d}-m$, and try brute-force starting from there.

# Answer
> 3 votes
You can compute $m,s$ from the equations: $s = (c-1)/2$ and $m = (b-1)/s$; both must be integral. You can then check that indeed $m(s+1) = a$. If this holds, then you have found the unique solution $m,s$, otherwise there is no solution. More generally, this method allows you to find the unique *real* solution to your system of equations, if any exists.

Note that $m = (b-1)/s = 2(b-1)/(c-1)$. Hence $s,m$ are integers if $s$ is odd and $c-1$ divides $2(b-1)$. If they are integers, the final equation is satisfied if $$ a = ms + m = b-1 + \frac{2(b-1)}{c-1} = (b-1) \frac{c+1}{c-1}. $$ Another way to state this condition is $$ a(c-1) = (b-1)(c+1). $$

---
Tags: algorithms, complexity-theory, integers
---


# Question
Title: How profiling is done in trace scheduling?
I'm trying to understand how trace scheduling works. The book that I'm reading, *Engineering a Compiler by Keith D. Cooper & Linda Torczon*, states that this method is using profiling. Profiling ranks each edge if the CFG by its frequency of execution. In other words the more a particular edge is followed the higher rank it has. So basically first the algorithm profiles the CFG and then runs trace scheduling. The only way (in my view) to do profiling is to run the code so that each edge of the CFG can be ranked. Somehow I don't think this is being done.

Here are my questions:

So how is profiling done?
Does the compiler guess the rank of each edge?
If it does, then what is the foundation for the guess?

# Answer
Yes, profiling is normally done by running the program. Yes, running the program and then gathering information about execution frequencies is how this is normally done. As Paul A. Clayton suggests, read more about profile-guided optimization to learn more about techniques commonly used in this field -- there's a rich literature on profile-guided optimization.

There *are* alternatives based on various heuristics or static analysis algorithms, but profiling normally implies running the program, and profiling will usually be considerably more accurate than any static technique.
> 2 votes

---
Tags: compilers, scheduling
---


title: Divide and Conquer 3D Convex Hull

text:
# Question
Title: Divide and Conquer 3D Convex Hull
http://cs.jhu.edu/~misha/Spring14/Preparata77.pdf

This is a divide and conquer algorithm for computing the convex hull in 3 dimensions.

I am having trouble understanding the merge step, which is titled Merge in 3 Dimensions, outlined in the paper.

I am specifically having trouble understanding how the number of comparisons made is done in O(n) time for the whole hull.

On page 92 in the last paragraph on the left column, it says that the number of comparisons made is bounded by the number of edges which is linear for each hull. But what if each vertex had p edges (so you are checking duplicates), then that would add up to quadratic running time. Or, if the number of edges each time was monotonically increasing from 1 to p-1, that still adds up to quadratic running time for the comparisons. For instance, a tetrahedron has 4 vertices and each vertex has a degree of 3, so the number of comparisons made would be 12.

# Answer
> 2 votes
The paper explains why the number of comparisons is $O(n)$ in the next few sentences immediately after the statement you're asking for a justification of. Just keep reading for a few more sentences, and you'll immediately find the justification. As it says,

> "First of all, we notice that each type 1 comparison definitively eliminates one edge ... Since the numbers of edges of A and B are at most $(3p-6)$ and $(3q-6)$, respectively, the number of type 1 comparisons is bounded by ..."

and so on. So to find the explanation for that statement, just continue reading a few sentences onward.

---

And, as the paper says in the introduction,

> "\[our algorithm\]" is based on the property that the number of edges of the convex hull of $n$ points is at most linear in $n$."

Therefore, your examples are not possible.

See also the 3rd paragraph of Section 4 for more elaboration ("It is a crucial observation that...").

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


title: Where is Program Counter (PC) stored?

text:
# Question
Title: Where is Program Counter (PC) stored?
Where is program counter stored? CPU caches?

Also how big are these counters?

What happens if that memory has been filled up?

I know that it's a value that stores the next instruction for the CPU to process, as well as it increments with the size of the next instruction to cycle for the next instruction for the CPU to process, and the cycle continues, that's as far as I know, right?

# Answer
> 7 votes
Inside a modern high-end CPU, the "program counter" is probably not stored in a single place. Superscalar out-of-order execution requires more than one instruction to be executing at a single time, some of them executing speculatively.

To understand what's going on, you need to consider what the program counter is used for. I'm going to use the Intel Core 2 microarchitecture as an example, mostly because it's the only decent-but-uncluttered diagram that I could find. Most modern high-end CPUs are broadly similar, in that they have a Tomasulo-like pipeline with register renaming. A RISC (e.g. MIPS or ARM) might have fewer decode stages. Also, not all CPUs implement a retirement register file; there are other methods which do the same job.

Nonetheless, let's go with this for the moment.

Instructions are (broadly speaking) streamed from the top to the bottom of the diagram. They start in the cache (and of course may have to be fetched into the cache), go through decoding and being stored in different buffers, until they end up in the reservation station. Here it waits until it is ready to execute.

When everything that an instruction needs becomes available, it goes to an execution unit. In the diagram, the yellow parts are the "normal" execution units (integer, floating point). There are also execution units for memory operations, but we'll ignore those for the purpose of this discussion.

When an instruction has finished execution, the results are posted on the results bus (called the "common data bus" in Tomasulo's original paper). These results may wake up instructions which depend on those results, and the cycle continues.

Now, think for a moment about what the program counter is used for.

First off, let's think about instruction fetch. It needs to know what address to send to the instruction cache for lookup. Most of the time, it's the next address. However, do consider that the cache line width isn't a single instruction; in this example it's 128 bits. So the instruction fetch unit actually increments its "program counter" by 16 bytes, no matter how big each instruction is.

Branch instructions complicate instruction fetch. Unconditional branches are straightforward once you've recognised them, so the instruction fetch unit gets some input from pre-decoded instructions.

Conditional branches are similar, except that the instruction fetch unit needs to decide whether to guess that the branch was taken or not taken to keep instructions flowing.

So the IFU has an idea about what the "program counter" is, but it is granular, working on a cache line at a time.

Now let's think about execution. The CPU would like to execute instructions out of order if it can, however things can happen which complicate that. The most obvious problem is if the IFU incorrectly predicted a conditional branch. However, instructions can also raise exceptions, and also the CPU might need to respond to an external interrupt.

To achieve this, the CPU needs to be able to recreate the CPU state as if it was executing instructions sequentially at the time that the control flow was interrupted. This is the job of the reorder buffer.

The reorder buffer is conceptually a queue of instructions, ordered by the "logical order" (i.e. the order that they would be executed if this was a scalar in-order processor). An instruction enters the queue as it travels down the fetch-and-decode path. Once it is in the ROB, it can execute out-of-order.

When an instruction completes, its entry in the ROB is updated noting that it is now complete. An instruction can leave the queue (it is "retired") if it has completed, and every instruction before it in logical order has completed or retired.

The "result" of many instructions is to write a value into a register. If that value is used by a subsequent instruction which is awaiting execution (i.e. it's in the reservation station), then this is handled by the internal results bus. Either way, the result is also stored in the instruction's entry in the ROB. This arrow is not shown on the diagram, but it happens.

When an instruction retires, any register write that it does is stored into the retirement register file. Because instructions are retired in-order, this register file actually stores the state of the machine registers exactly as they would be if the instructions were executed in-order. This is why it's also called the "program visible state". This is the view of the registers that the program "sees", what is saved and restored on a context switch, and so on.

So the second place where there the "program counter" is stored is here, in the instruction retirement unit. This is the program counter as the program sees it, without any speculation, but it's decoupled from instructions that are being fetched and executed.

As an aside, the ROB is also how faults and exceptions are handled. If a fault occurs, then the ROB for the faulting instruction is updated with information about the fault, and every instruction after it in the ROB is removed, along with a flush of the fetch-and-decode parts of the pipeline. This ensures that instructions after the fault don't "happen" even if they have been executed already: the results of those instructions never make it to the program-visible state. Speculative execution is handled in a similar way.

A third place where the program counter may be stored is in the ROB itself. It may be convenient to store the program counter of each instruction along with the instruction. Note that it may not be necessary to store the whole program counter; it may be sufficient to store enough information to recreate the program counter as needed.

A final place where the program counter may be stored is as a general-purpose register. Exactly what this means is a bit complicated to explain if you don't know how register renaming works, but some instructions might need the value of the program counter (e.g. it might be used for memory addressing in position-independent code), in which case transient copies may be stored in reservation station entries of instructions which use it.

So what I hope you can see here is that the real answer is "it's complicated". The program counter is different from other registers in a modern CPU, and there is no one place where it's really "stored", because more than one instruction is "happening" at any given point in time.

# Answer
> 5 votes
Program Counter is a register in the CPU hardware.

Effectively it's a digital counter so consists of binary latches where each latch represents a binary bit. Number of latches,ie the size of the PC depends on the processor architecture.

If overflow takes place in a Program Counter it simply wraps around, like a normal ring counter. For example if PC has a capacity of 100, it counts from 0 to 99. At 100 it goes back to 0. AT 101 value stored in PC is 1.

---
Tags: computer-architecture
---


# Question
Title: Constructive proof of decidability of finite Halting-problem-style set that does not use table lookup
I tried to prove that the following language is recursive: for $\Sigma=\\{0,1\\}$, $k$ a positive integer: $$ L\_k= H\_{\mathrm{TM},\varepsilon}\cap \Sigma^k $$ where $H\_{\mathrm{TM},\varepsilon}=\\{\langle M\rangle\mid M \text{ is a TM that halts on an empty input}\\}$

It is easy to prove because $L\_k$ is finite, but I didn't notice this and tried to prove it by finding a decider TM for it. I thought that since the encoding of the TM is of length $k$ then it can't have more than $2^k$ states, and by running it on epsilon for $2^k$ steps, if it halts by then than accept otherwise reject. I was told that it's incorrect - is it a wrong solution. How can I prove this using this method (and not the way I mentioned about $L\_k$ being finite)?

# Answer
> 10 votes
## There is no general way to find a decider TM for $L\_k$

You are correct that $L\_k$ is recursive because, being a subset of the finite set $\Sigma^k$, it is also finite.

You would like to rather find a decider TM for $L\_k$, and you suggest some techniques. Without even going into the details of these techniques and why they do not work, you do not stand any chance of ever succeeding.

The first thing you should notice is that the finiteness argument tells you that there exists a decider TM $M\_k$ for the language $L\_k$, but it does not tell you what this TM is. It is an example of a non-constructive proof: you prove that a decider exists, but you cannot tell which it is.

Now, suppose that, given $k$, you have a procedure $\mathcal P(k)$ to find such a decider $M\_k$ for the language $L\_k$ (rather than just prove it exist). Then, given any Turing machine $M$, then there is an integer $k'$ such that $|\langle M\rangle|=k'$, so that $\langle M\rangle\in \Sigma^{k'}$. Then you can use the procedure $\mathcal P$ to find a decider TM $M\_{k'}$ that can determine whether $\langle M\rangle\in L\_{k'}$. So you have a way to decide whether the TM $M$ halts on empty input. And this works for any TM $M$. However, this is not possible, because it is undecidable whether a given TM $M$ halts on empty input.

So the procedure $\mathcal P$ cannot exist.

Since you are looking for a general way to find the decider TM $M\_{k'}$, you cannot succeed because that method would be precisely a procedure such as $\mathcal P$.

Note that this proof could still leave the (very remote) possibility of finding a decider for some specific values of $k$, but you would have to identify precisely the concerned values, and the method would not work for all values of $k$. I am not advising you to try.

# Answer
> 6 votes
You can "fix" your proof using the busy beaver function. Let $B\_k$ be the maximal number of steps that a Turing machine of description size at most $k$ performs before halting, when given the empty input. If you know $B\_k$ (or even just an upper bound on $B\_k$, that is, some $T\_k \geq B\_k$) then you can solve the halting problems for Turing machines of description size $k$ (and the empty input) by running the given machine for up to $B\_k$ (or $T\_k$) steps. If it doesn't halt by that point, then you know that it never halts.

Since the halting problem isn't decidable, we know that the function $B\_k$ cannot be computable. Indeed, no computable function $T\_k$ satisfies $T\_k \geq B\_k$ for all $k$. In other words, for any computable function $f(k)$, it is the case that $B\_k \> f(k)$ for infinitely many $k$. Roughly speaking, $B\_k$ grows faster than every computable function.

In fact, using diagonalization one can show that $B\_k$ does grow faster than every computable function: for every computable $f(k)$ there exists $K$ such that $B\_k \> f(k)$ for *all* $k \geq K$. This was first proved by Rado.

---

# Answer
> 4 votes
The core fallacy is that you assume that the number of states a TM has limits its runtime (before termination) in some way. This is false.

Case in point, there are *universal Turing machines*, that is finitely described TMs that can exhibit *any* behaviour, from terminating quickly over running arbitrarily long to looping, given the right input.

On a technical note, universal TMs are usually described as taking two parameters, one TM encoding and the input to simulate it on. It is easy to merge them into one parameter, so there are indeed unary universal TMs.

More specifically, you ignore the *input* of the encoded TM, which can be arbitrarily large (and convoluted). The actual state of a TM is the product of control state *and* tape content, so a simple combinatorial argument based on the number of control states alone is not sufficient. In particular, a TM is not in an unescapable loop when it visits some state for the second time.

---
Tags: computability, turing-machines, proof-techniques
---


# Question
Title: What algorithm to use to generate random path of given length
I have a map size of 8 x 8 cells with no obstacles. I should generate random path from start cell to the end cell with given length. Path can move up/down/left/right directions but not cross itself. What algorithm I can use to do this?

# Answer
> 1 votes
# Algo for solving problem when path self-intersections are allowed

## Auxiliary problem

First let's solve another problem:

> How many paths of length $K$ exists starting at coordinate $(StartRow, StartColumn)$.

Such problem can be solved by dynamic programming: let $dp\[K\]\[R\]\[C\]$ be answer for question:

> How many paths of length $K$ exists that start in $(StartRow, StartColumn)$ and ends in $(R, C)$".

Base case: $$ dp\[0\]\[StartRow\]\[StartColumn\] = 1 $$

Step of dynamic: $$ dp\[K\]\[R\]\[C\] = dp\[K-1\]\[R-1\]\[C\] + dp\[K-1\]\[R+1\]\[C\] + dp\[K-1\]\[R\]\[C-1\] + dp\[K-1\]\[R\]\[C+1\] $$

Here we suppose $dp\[K\]\[X\]\[Y\]=0$, for any $X$ and $Y$ that outside of grid (e.g. $X \< 1$ or $X \> N$ or $Y \< 1$ or $Y \> N$) Also we can even add more constraints for problem and add obstacles: for doing so - we need to suppose $dp\[K\]\[R\]\[C\]=0, \forall K$, where cell $(R, C)$ is impassable (e.g. is obstacle).

This will take $O(N\*M\*K)$ time, where $N$ - number of rows, $M$ - number of columns, and $O(N\*M\*K)$ memory if we will keep all steps of dynamic or $O(N\*M)$ if we will keep only last step of dynamic.

## Original problem

> Generate random path of length $K$ between cells $S(R\_s, C\_s)$ and $E(R\_e, C\_e)$.

1. First of all we need count how many paths of length $K$ exists between this cells, for that we can use previously described dynamic: futhermore run it from end cell (e.g. count how many paths of length $K$ exist that start at $(R\_e, C\_e)$) and save all step of dynamic (we will use it in next steps).
2. Now add order relation between all paths of length $K$ starting at cell $(R, C)$ and ending at cell $E(R\_e, C\_e)$:

* if $K=0$ we have $0$ or $1$ such paths (such collection is always ordered);
    * if $K\>0$ let's suppose: `Paths that go UP` $\<$ `Paths that go RIGHT` $\<$ `Paths that go DOWN` $\<$ `Paths that go LEFT` (and for ordering paths in each of 4 groups we can recursevly apply this definition again).
3. Then we know how many paths of length $K$ exist between cells $S$ and $E$, lets name it $A=dp\[k\]\[R\_s\]\[C\_s\]$, now we can uniformly at random peek number $L\in\[0, A)$ that will identify choosen path among all $A$ available.
4. We had ordered all $A$ paths and choose some path to output $L$ ($0-indexed$) and just need to find it. Let $choose(R\_c, C\_c, L, K)$ - function that return $Lth$ path of length $K$ staring at cell $(R\_c, C\_c)$ and ending at $E(R\_e, C\_e)$:

$$ choose(R\_c, C\_c, L, K) =\small\left\\{ \begin{array}{ll} \langle empty \rangle, K = 0\\ \langle UP, choose(R\_c - 1, C\_c, L - 0, K - 1)\rangle, \\ \hspace{45pt} L \in \[0, Count\_u)\\ \langle RIGHT, choose(R\_c, C\_c + 1, L - Count\_u, K - 1)\rangle, \\ \hspace{45pt} L \in \[Count\_u, Count\_u + Count\_l)\\ \langle DOWN, choose(R\_c + 1, C\_c, L - (Count\_u + Count\_l), K - 1)\rangle, \\ \hspace{45pt} L \in \[Count\_u + Count\_l, Count\_u + Count\_l + Count\_d)\\ \langle LEFT, choose(R\_c, C\_c - 1, L - (Count\_u + Count\_l + Count\_d), K - 1)\rangle, \\ \hspace{45pt} L \in \[Count\_u + Count\_l + Count\_d, A)\\ \end{array} \right.\\ $$ $$ Where \forall K, R\_c, C\_c\\ Count\_u=dp\[K - 1\]\[R\_c - 1\]\[C\_c\]\\ Count\_l=dp\[K - 1\]\[R\_c\]\[C\_c + 1\]\\ Count\_d=dp\[K - 1\]\[R\_c + 1\]\[C\_c\]\\ Count\_r=dp\[K - 1\]\[R\_c\]\[C\_c - 1\]\\ $$

And $Count\_u$ means how many paths of length $K$ starts at $(R\_c, C\_c)$ and ends at $(R\_e, C\_e)$ and first move is $UP$, $Count\_l$, $Count\_d$, $Count\_r$ defines respectively for another directions.

More intuitively, imagine we at $X$ cell choosing for $7th$ path:

`...
_ 4 _
5 X 0
_ 9 _
...`

If we go $UP$ we will follow paths $\in \[0, 4)$, there is no paths to $RIGHT$, if we go $DOWN$ we will follow paths $\in \[4, 4+9)$, so we need to go $DOWN$ and choose $(7 - 4)th$ path among all that starts in that cell.

**Note:** due to we define ordering on paths $I'th$ path everytime will be the same (so it's possible to store path just as index number among all such paths and restore path when it is needed). Also need to notice that order $UP \< RIGHT \< DOWN \< LEFT$ is not only right choise, you can use any order - just keep it thorugh all algorithm flow the same.

---
Tags: algorithms
---


# Question
Title: Comparison between Aho-Corasick algorithm and Rabin-Karp algorithm
I am working on string searching algorithms that support multiple pattern search. I found two algorithms that seem like the strongest candidates in terms of running time, namely Aho-Corasick and Rabin-Karp. However, I could not find any comprehensive comparison between the two algorithms. Which algorithm is more efficient? Also, which one is more suitable for parallel computing and multiple patterns search? Finally, which one requires less hardware resources?

For AC algorithm, the searching phase takes $O(n+m)$ time, while it is $O(nm)$ for RK. However, the running time for RK is $O(n+m)$ which makes it similar to AC. My tentative conclusion is that RK seems practically better as it does not need as much memory as AC. Is that correct?

# Answer
Asymptotic running time analysis is not likely to be the best tool to pick between these two algorithms: asymptotic analysis ignores constant factors, and the constant factors will be critical here. The two algorithms have basically the same asymptotic running time, so asymptotic analysis probably isn't very helpful to choose between them.

Instead, the right way pick between the two algorithms is through experimental analysis. Identify a representative workload, and then benchmark the performance of both algorithms on your workload, on the kinds of machines you intend to use in practice.

---

Incidentally, it sounds like you might have a slight confusion about the asymptotic running time of Rabin-Karp. On the one hand you say that Rabin-Karp has $O(nm)$ running time, but then in the next sentence you say Rabin-Karp has $O(n+m)$ running time. Perhaps you are confused by the difference between expected (average-case) vs worst-case running time.

Since Rabin-Karp is randomized, expected (average-case) running time is the appropriate metric to use to predict real-world performance in practice. In particular, here the average is taken over the random choice of hash function. It's specifically *not* an average taken over the choice of strings. Even for the worst possible string and pattern, the average running time will still be $O(n+m)$. With a suitable hash function, the probability that the running time is longer than $c\cdot(n+m)$ is exponentially small in $c$. To put it another way (and being slightly informal), there's only an exponentially small chance that Rabin-Karp takes longer than $O(n+m)$ time. We already have to accept exponentially small chances of bad things happen -- for instance, there's a tiny but non-zero chance of a cosmic ray causing a bit-flip in your memory that causes the program to loop forever. So, worrying about this exponentially small chance makes no sense.

From an engineering point of view, Rabin-Karp's running time *is* $O(n+m)$ \[or it might as well be\]. Ignore the $O(nm)$ stuff; that's not really relevant to practice.
> 6 votes

# Answer
> However, I could not find any comprehensive comparison between the two algorithms.

a question like this on relative performance of two algorithms generally depends on average case versus worst case which is dependent on actual data. the theoretical answer is that the $O(n + m)$ Aho-Corasick algorithm will outperform $O(n m)$ Rabin-Karp in the large data limit case/ asymptotically, but where that limit is reached is implementation and data dependent & the tradeoff between searching/ running times.

but wrt your implicit query for "comprehensive comparison", some papers have been written experimentally/ empirically comparing these two and other algorithms on real data and include analysis/ comparison of the pros/ cons/ tradeoffs of the different algorithms eg:
> 1 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis, strings
---


# Question
Title: Find minimum value at each index after queries which tell you minimum value over a range
Assume that initially in array each element has infinity as value.

Now M queries are input of the type l r x.

Here l to r is range where value need to be updated if a\[i\]\>x where l\<=i\<=r. and l\<=r\<=n

After M queries you need to output the minimum value at each index.

One way to this is to use Brute Force

```
memset(a,inf,sizeof(a));
while(j<m)
 {
     scanf("%d %d %d",&l,&r,&c);
     for(i=l-1;i<r;i++)
     {
            if(a[i]>c )
                a[i]=c;

     }

     j++;
 }

```

Now this takes O(mn) time where n=size of each query which can be n in worst case.

What are more efficient ways to solve this in lesser time complexity?

# Answer
> 0 votes
It can be done by using Segment Tree data structure:

1. Originally described query is just "lowering values at some segment", so let's call it **update query**. To perform this query you need to update at most $O(\log N)$ segments and it also can be done with $O(\log N)$ time-complexity. So for run all **update queries** we need $O(N \log N)$ time.
2. We have another type of **query** "what is the value at $a\[i\]$. In general we can answer to such query with $O(\log N)$ time, by going through all segments that contains $a\[i\]$ and take minimum from such values and due to nature of segment tree there will be at most $\lceil log N \rceil$ such segments. At this point we have online solution (e.g. queries of 1st and 2nd types can be mixed). Also gathering resulting array after all queries of 1st type (e.g. offline solution that asked in original post) can be performed even with *linear* complexity (relatively to array length); please, note that it's time complexity only for constructing result array by segment tree, for performing $N$ queries we still need $O(N \log N)$ time.

For example:

1. To perform **update query** on segment $\[1, 4\]$ you need to update pink nodes.
2. To know what is value at $a\[4\]$ you need to go through all segments rounded by yellow and takes minimum from values at this segments.

---
Tags: algorithms, arrays
---


# Question
Title: Question as regards a proof of the Time Hierarchy Theorem
I'm referring to the proof outlined here (and wikipedia.org): https://proofwiki.org/wiki/Deterministic\_Time\_Hierarchy\_Theorem

In my understanding, if I relaxed the conditions such that $K$ decides the input in time $O(f(m)^3)$, there should not be a contradiction in the final step because an appropriate TM $K$ should really exist.

Under this condition, $N$'s running time should be $O(f(2n+1)^3)$.

Finally, I arrive at the conclusion:

1. If $N$ rejects $\[N\]$ (which we know it does in at most $f(2n+1)^3$ operations):
2. By the definition of $N$, $K$ accepts $(\[N\],\[N\])$.
3. Therefore, by the definition of $K$, $(\[N\],\[N\])\in H\_f$.
4. Therefore, by the definition of $H\_f$, $N$ does accept $\[N\]$ in $f(n)$ steps.

To me it seems that 1. and 4. would still contradict. What did I do wrong?

# Answer
Your arguments is as follows:

1. If $N$ rejects $\[N\]$ then $(\[N\],\[N\]) \in H\_f$.
2. Since $(\[N\],\[N\]) \in H\_f$, $N$ accepts $\[N\]$ in $f(m\_n)$ steps.

This is indeed a contradiction, so we conclude that $N$ accepts $\[N\]$. Then we argue again:

1. Since $N$ accepts $\[N\]$ then $(\[N\],\[N\]) \notin H\_f$.
2. Since $(\[N\],\[N\]) \notin H\_f$, it is not true that $N$ accepts $\[N\]$ in $f(m\_n)$ steps.

Since the running time of $N$ is $f(2m\_n+1)^3$ in your case, there is no contradiction. After $f(m\_n)$ steps the machine $N$ might still be running.
> 3 votes

---
Tags: complexity-theory, time-complexity
---


# Question
Title: Calculating the number of multiplications necessary to evaluate a polynomial
I was watching a lecture and got confused over a slide. This is what it says:

> Consider a polynomial - first representation
>
> $$P = 2 + 4x^{3} + 8x^{6} + 7x^{25} + 6x^{99}$$
>
> * The space complexity is 100 memory locations.
> * The time complexity is:
>     + Access lookup operations: 100
>     + Multiplication operations: 4 + 7 + 26 + 100 = 137
>     + Addition operations: 5
>     + Total operations: 242

I don't get how the number of multiplication operations are counted. For example, if we consider $x^{3}$ then it should have just two multiplications, right? Such as $x \times x \times x$, isn't it?

Addition operation is 5 or 4...I think its 4?

# Answer
I am not sure what the slide was intended for, so I just gave a straight answer to your question in a comment, viz that the slide really intended 3 multiplications for $4x^3=4\times x\times x\times x$, and 4 additions to add the five terms.

Now of course, there are better ways to do that. Various powers of $x$ can be obtained in multiplying other powers of $x$ together using the rule $x^m\times x^n=x^{m+n}$.

The method of repeated squaring presente by David Richerby in his answer is a systematic way to get high powers of $x$ as fast as possible. However, when you need a few specific powers, you can try to adapt it to compute just these powers with as few multiplications as possible.

So you can compute, for example:

$\begin{align} x^2&=x\times x \\ x^3&=x^2\times x \\ x^6&=x^3\times x^3 \\ x^{12}&=x^6\times x^6 \\ x^{24}&=x^{12}\times x^{12} \\ x^{25}&=x^{24}\times x \\ x^{49}&=x^{24}\times x^{25} \\ x^{50}&=x^{25}\times x^{25} \\ x^{99}&=x^{49}\times x^{50} \end{align}$

Hence you get all needed powers of $x$ with only 9 multiplications of powers of $x$, to which you have to add 4 multiplications for the coefficients, which makes a total of 13 multiplications. The number of additions remains at 4.

But you can do a bit better using a technique that is most efficient when all powers of $x$ are being used, rather than having a sparse polynomial. The technique, known as Horner's method, consists in factorizing some powers of the variable, when it helps the computation.

In the case of your sparse polynomial, you may notice that $7x^{25}+6x^{99}=x^{25}(7+6x^{74})$. Hence rather than computing $x^{50}$ and $x^{99}$, you compute only

$x^{74}=x^{49}\times x^{25}$ and then $x^{25}(7+6x^{74})$.

This saves one multiplication, because both $7x^{25}+6x^{99}$ and $x^{25}(7+6x^{74})$ take exactly 2 multiplications and one addition, assuming the powers of $x$ are already computed, but computing the needed powers takes one less multiplication.

So you are down to a total of 12 multiplications and 4 additions.

I do not see any way to do better on this example, but I have no systematic algorithm to check that. However, I am rather confident that someone must have worked on it.

BTW, what was the theme of the set of slides?
> 5 votes

# Answer
Yes, there's an error on the slide: as you say, there are only four addition operations (count the plus signs!) and, e.g., computing $4x^3 = 4\times x\times x\times x$ requires only three multiplications, not four.

However, there is a more significant point to be made, which is that computing, say, $8x^6$ does not require six multiplications. We have $8x^6 = 8\times z\times z\times z$, where $z = x^2$. This requires only four multiplications: one to compute $z$ and then three more to compute $8z^3$. And $x^{99} = z\_0\times z\_1 \times z\_5\times z\_6$, where $$z\_i = x^{2^i} = \begin{cases} x &\text{if $i=0$}\\ z\_{i-1}^2 &\text{otherwise.}\end{cases}$$ So this can be computed with only nine multiplications (six to produce $z\_1, \dots, z\_6$ and three more to compute $x^{99}$ from those. This technique is known as exponentiation by (repeated) squaring.
> 3 votes

# Answer
I think they are multiplying the constants too.

1. 4\*x...\*x (3 times)= 3
2. 8\*x\*....\*x(6 times)= 6
3. 7\*x\*....\*x(25 times)= 25
4. 6\*x\*....\*x (99 times)= 99

Addition operations are 4.
> 0 votes

# Answer
The claims of this slide seem bizarre.

First, even using repeated multiplication to calculate powers, x^99 requires 98 multiplications, and 6x^99 requires 99. Not 100.

But then you would use the result of x^25, so x^99 would only require 74 more multiplications. With 98 multiplications, you get *all* the required powers, and with the four coefficients, it makes a total of 102 multiplications and 4 additions.

But nobody would calculate x^99 that way. See babou's post.

Now if all coefficients were non-zero, it seems their method would use about 5,000 multiplications, which is just ridiculous.
> 0 votes

---
Tags: algorithm-analysis, arithmetic, polynomials
---


# Question
Title: Reduction of SUBSET-SUM to SET-PARTITION
There is a similar question that has been asked, but my question addresses particular detail of an answer.

I am trying to reduce SUBSET-SUM to SET-PARTITION. I found the following description:

SUBSET-SUM is defined as follows: Given a set `X` of integers and a target number `t`, find a subset `Y` from `X` such that the members of `Y` add up to exactly `t`. Let `s` be the sum of members of `X`. Feed `X' = X U {s - 2t}` into SET-PARTITION. Accept if and only if SET-PARTITION accepts.

What does "`X' = X U {s - 2t}`" (union?) and "Feed `X' = X U {s - 2t}` into SET-PARTITION" mean? How does this prove that SUBSET-SUM can be reduced to SET-PARTITION?

# Answer
What you are doing here is adding a new element to your original set 'X'. The value for this new element is (s - 2t). Hence, X' now contains one extra element as compared to X.

The SET-PARTITION would "accept" if the provided set can be partitioned into two subsets with equal sum. We were already able to pick out a subset 'Y', from the set X, the sum of whose elements was 't'. If we include the extra element (s-2t) in this subset Y, the sum of its elements would now become ( t + s - 2\*t ) = (s-t). This is also the sum of the elements which are remaining in the set (X - Y). Hence, X' can be divided into two subsets each of whose sum is (s-t).
> 2 votes

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


# Question
Title: How can I compute the time complexity of this image processing algorithm?
Well, my question is simple, I would like to compute the complexity time of an algorithm related to image processing.

I simplified the algorithm ... so that we focus only on the problematic part.

## Algorithm

You have an image/matrix of $N =n \times m$ size and a block of size $b \times b$ (block is just a window or rectangle that will slid through the picture of pixels or the matrix of intensities).

The algorithm goes through most pixels in the image (as center of the block, so it may step over the end of the line or the beginning) by a *step* of size $s$. The step is inferior to the size of the block $s\<b$, so there is some overlapping (because some pixels are being considered in multiple blocks), and then it performs some operations with a complexity relative to the size $b$ equals $O(b^2)$.

Concretely, the algorithm starts in line $1$, and process blocks starting at $1, s+1, 2s+1, ... $ columns, then it goes to the $s+1$ line and do the same as on line $1$, then to $2s+1$ line and so on. Every iteration, the algorithm computes some operations related to the size of the block (which can be $3 \times3$ or $5 \times 5$, ... and $s$ is $1/8$ the $b$ for instance).

---

Any help, or reference related to this topic is a welcome.

# Answer
> 3 votes
We need to estimate how many times block operation is performed.

1. First lets answer in how many rows we will start **block processing** \- easy to see that each $S$ row are taken into account, so answer to this sub-question is $O(N/S)$. *If we suppose that $N$ - number fo rows and $M$ number of columns.*
2. Then we need answer to question - how many times we will run **block processing** for each row, due to we perform processing of blocks that starts only in each $S$ columns - answer for this sub-question will be $O(M/S)$.

Now we have that **block processing** will be performe $O(N\*M/S^2)$ times for whole input. And result time-complexity for whole algorithm will be $O(N\*M\*B^2/S^2)$.

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


title: "Practical" bounding box?

text:
# Question
Title: "Practical" bounding box?
For the sake of simplicity, lets say I have a bunch of 2d points, each have X and Y. The points are distributed somewhat randomly but not completely, they will be biased to be closer to the world center (where ever that might be, completely random) and they are likely to have some kind of a shape. You can imagine that like a bunch of stars forming a galaxy around a black hole...

Now I need to process these points (each of them have a lot of calculations) and to optimize the processing, it would greatly help if I knew whether they were north of most of the other points or south, east or west and nort/south more or less than east/west. The exact specifity of the distribution is not important, right now I'm imagining 8 sectors (NNE, NEE, SEE, SSE, SSW, SWW, NWW, NNW like on the map).

2 simple but incomplete solutions to this are:

1. average the position of all the points creating the center of the collection and compare the position of each point to that. This has 2 problems. For one, 99% of the points could be in a tight circular group while one point could be waay far out somewhere. This would shift the center towards that point and in the worst case scenario, the 99% of the points would only be distributed between 2 sectors. Second problem is that the distribution doesn't have to be circular, they are just as likely to show up in the shape of a giraffe. Due to the long neck on the giraffe, the Y amplitude would be much greater than X so the processing will be incorrectly biased 50% of the time between X or Y.
2. Also compare the x and y of each point to a global min/max creating a bounding box, the bounding box can then be used to normalize x/y distribution but would suffer even more from the one lone point that could be way out there.

So in essence, I'm looking for a way to find the average position and the bounding box without being affected by the potential flyaway. The quality of those 2 pieces of data would be defined as follows: After cutting the BB into 8 sectors like a pie originating from the center point, if a point is assigned to the NNE sector for example then

1. the greatest percentage of other points must be towards its south
2. the second greatest towards its west
3. the third greatest towards its east
4. and least amount of points towards its north

Any ideas?

# Answer
> 1 votes
For all I can understand of your problem, you want to find a median point serving as center such that half your points are north, half south, half west, half east.

This is not a center of gravity, since distances do not seem to matter. This can be done by computing separately the median for all $X$s and for all $Y$s. There are no giraffe effect, or lone star effect, or other.

Computing this median $X\_M$ and $Y\_M$ for all $X$s and $Y$s can be done in linear time $O(n)$ where $n$ is the number of points, as indicated in wikipedia and StackOverflow.

Then for any point $(X,Y)$ you can know whether it has more points south (low ordinates) by checking whether $Y \> Y\_M$, and conversely for more points north.

Similarly by comparing $X$ to $X\_M$ you can tell whether ther are more points east or west of point $(X,Y)$

You can get similar results along any direction.

# Answer
> 0 votes
If I understand your problem statement, this can be solved efficiently using sorting. Simply sort all of the points by their Y coordinate, and for each point, remember its index in the sorted order. Now, for any given point, you can quickly identify where in the sorted list is, which immediately tells you how many points are north of it. In particular, if the node is in the last half of the list, then it's north of at least 50% of the points. So, this lets you solve your question immediately.

The running time will be $O(n \lg n)$, the time to sort all of the points.

You can do a similar computation to find the points that are east of at least 50% of the points (simply use the X coordinate instead of the Y coordinate), or the points that are north-east of at least 50% of the points (rotate the coordinate system by 45 degrees, then do the same thing), and so on. So, this lets you accomplish each of your goals.

---
Tags: computational-geometry, statistics
---


# Question
Title: Computing the number of squares which are intersected by a line internally
There's a line from (x1,y1) to (x2,y2) in a grid of squares of unit length. Write a program to compute the number of squares which are intersected by the line internally, i.e squares which are only touched by the line should not be counted. Notes x1,y1,x2,y2 are all integers. 0 \<= x1,y1,x2,y2 \<= 10000 Write the program so that it accepts 4 command line parameters - x1,y1,x2,y2 The output of the program should be a single line consisting of only the integer output Example: Input (x1 y1 x2 y2): 1 1 6 6 Output (No. of squares): 5

please help me to understand how these squares will generate? do i need to predefined all the squares in a 2d matrix form?

# Answer
As the question says, the program should be as follows:

### INPUT:

4 integer numbers: $(x\_1,y\_1)$, $(x\_2,y\_2)$

### OUTPUT:

a single number $n$.

$n$ should be the number of squares that are touched by a line that starts at $(x\_1,y\_1)$ and ends at $(x\_2,y\_2)$. Assuming the squares are of length 1, and the first square has corners at (0,0), (1,0), (0,1), (1,1).

That's it. Nobody gives you the squares as a matrix or any other form. They are not in the memory, and nobody tells you how to construct them. Furthermore, your program DOES NOT NEED to construct the squares. It can, but it needs not. The output $n$ can be found in a purely mathematical way.
> 1 votes

---
Tags: algorithms, computational-geometry, arithmetic, graphics
---


# Question
Title: Order-preserving update of a sublist of a list of mutable objects in sublinear time
## Description

Say I have a source list like: `["a","b","c","d"]` and want to run a capitalization filter so if I change, `"b"` to `"B"`, my derived list looks like `["B"]`. Next, if I change my source list's `"d"` to `"D"`, the derived list should look like `["B","D"]`.

Is it possible to make the insertions and removals in the derived list, while maintaining order, in faster than $O(n)$ time, $n$ being the size of the list?

Finally, I'd like to be able to **know the index of where the insertion or removal takes place** in the derived list in faster than $O(n)$ time.

## An idea that doesn't work

I could keep the derived list in a tree, sorted by the source index. This way, when I needed to insert my item in derived tree-list, it would take $O(log n)$. However, I would not be able to know that index of that insertion without walking the entire tree.

Thanks for your help!

## Problem Statement

* Let $S$ be an ordered list
* Let $Si.filterProperty$ be $true$ for some elements in $S$
* Let $F$ be an ordered list of all elements in $S$ where $Si.filterProperty$ is true

Let $T(i)$ be a function that:

* Sets $Si.filterProperty$ to $true$
* Inserts $Si$ into $F$, ordered in the same fashion as $S$
* Returns the index in $F$ where $Si$ was inserted

**Can $T$ and its side effects be faster than $O(n)$?**

Any list-like data structures can be used within these constraints:

* Insertion and side effects of insertion are faster than $O(n)$
* We must know the index of the newly inserted item into $F$

# Answer
*At the time of writing I was not absolutely sure what the problem was. This lead to a more general second answer. See details in discussion at the end of this answer.*

Apparently, the "idea that does not work" does not work because you do not know the index of an element $S\_i$ in $F$ organized as a tree.

This is what is addressed here. The problem is restated for clarity, as your statement of it is a bit hard to follow.

## Restatement of the problem:

Given a set $S$ with an order relation, maintain an ordered list $F$ where elements of $S$ can be inserted or removed, and such that the index of an element in $F$ is returned when the element is inserted.

Actually, the solution will do more, as it is possible to access any element of $F$ given its index, or to retrieve the index given an element of $F$. All operations are in time $\log n$.

## Solution:

You keep the ordered derived list $F$ in a self-balancing binary tree. I checked with AVL trees, but other types (such as red-black trees) should work as well. In each node $N$ of the tree you keep a count $\text{weight}(N)$ of the number of elements of $F$ in the subtree rooted in $N$, node $N$ included.

This can be done by updating weight counts as you walk down from the root of the AVL tree for $F$ to reach the place for the insertion or deletion. Then, during the retracing phase that rebalances the tree, when needed, you also update the weight counts according to the rebalancing. That only add constant cost to each elementary step, thus does not change the $\log n$ time complexity of the algorithm.

Hence it is easy to use this weight to compute in $\log n$ time the index of an element of the list $F$ when accessing it, either on the way down from the AVL tree root, or by walking up to the root when accessing the element directly.

The index is computed on the fly by adding the weights of all the immediate siblings on the left of the path from the AVL tree root to the concerned element of $F$.

Conversely, it is easy to find in $\log n$ time an element of $F$ from its (left to right) index by walking down from the root and leaving enough elements on the left.

## Computing the index of $S\_i$ in $F$ using weights:

Recall that the weight of a node $N$ is the number of nodes in the subtree rooted at $N$, node $N$ included.

Computing the index of $S\_i$ from the weights in the tree is precisely done as follows: you simply do a search for $S\_i$ in the standard way of binary search trees, with a modification to compute the index. Below is a pseudo-code recursive version, adapted from the searching algorithm in wikipedia. It raises an exception if $S\_i$ is not in the AVL tree, and the index count start at 0 for the first element. To have the count start at 1, the first return statement should be `return node.left.weight+1`.

```
function Find-recursive(S_i, node):  // call initially with node = root
    if node = Null then
        raise Key_Not_Found
    else if node.key = S_i then
        if node.left = Null then return 0
        else return node.left.weight
    else if key < node.key then
        return Find-recursive(key, node.left)
    else
        if node.left = Null then return Find-recursive(key, node.right)+1
        else return Find-recursive(key, node.right)+node.left.weight+1

```

When the path from the root goes to the right daughter, that means that all nodes in the left daugther subtree, plus the current node, precede $S\_i$, and have to be added to whatever other predecessors will be found while searching in the right daughter subtree.

I do not give here the modifications of the insertion and deletion code necessary to update the weight count, as this is a bit too long for an answer here, and not so hard to do.

## About the question, and the two proposed answers

The precise specification of the problem took some time to agree upon.

This **first answer** to the question was written on the basis of an initial specification that did not mention explicitly that the source list $S$ could be modified dynamically, by insertion or deletion, thus possibly inducing a similar modification in the filtered list $F$.

The elements of list $S$ are mutable objects and have a *filter-property* $P\_F$ that may be true or false depending on operations performed on an element. The purpose of the question is to maintain a sublist $F$ of elements $s\in S$ such that $P\_F(s)$, similarly ordered, such that the rank in $F$ of an element $s\in S$ is known when it in inserted in $F$ due to a mutation.

I assume in this first answer here that the list $S$ is constant, except for changes to its mutable elements. Thus on may see the list $S$ as a set (of list elements), totally ordered by the order of the list, and that relative order of two elements can be checked in constant time $O(1)$, for example by attaching its $S$-list rank to each element.

In a much later comment to this answer, the author of the question made it clear that he also wanted to be able to modify the list $S$ with insertion or deletion of elements. This more complex question is addressed separately in a **second answer**.

**Why keep both answers?** The first algorithm here is slightly more efficient as all operations can be performed in time $O(\log|F|)$, while the more general algorithm (second answer) requires time $O(\log|S|)$. With a constant ratio $|F|/|S|$, the difference is only an additive constant $\log|S|-\log|F|$. However this constant is to be compared to a logarithmic complexity $\log|F|$, which may not be very large itself. And this complexity is that of elementary operations on a data structure, to be repeated often in larger algorithms. So this apparently negligible difference may have a measurable impact on performance of a larger algorithm using the structure.

To see it numerically, assume that $|S|=256$ and $|F|=16$. Then $\log|S|=8$ and $\log|F|=4$, which give a performance ratio of $2$, to which one should add that the structure of the more general algorithm may be more costly to maintain.
> 3 votes

# Answer
What you're describing is a data structure for a set of integers with a rank operation. There are a number of published solutions with performance as good as O(1) on both queries and updates, for instance this recent paper.

These structures are fairly intricate, but generally they break the elements into blocks and maintain a summary rank for each block to use as a starting point. It's not much different from using a tree with leaf counts, but the space can be considerably smaller.

This blog post describes the basic ideas.
> 1 votes

# Answer
I have an answer that seems to work in *O(log N x log N)* time. However, I'm betting there's an answer in *O(log N)* time.

In short, I keep a **T** self-balancing tree that reflects the source list **S**. It keeps track of indexes using the "left count" approach @babou suggested. Every node also knows about its parent.

I also keep an **F** self-balancing tree that represents the filtered result, but with references to its symmetric nodes in **T**. This also uses "left count" on each node.

Together, it works as follows. Say **S** looks like:

```
S = [Z,b,c,e, f, G]

```

**T** might look like:

```
                   {v: c,LC: 2}
{v: Z, LC: 0}                      {v: f, LC: 1}
      {v: b, LC: 0}         {v: e, LC: 0}   {v: G, LC: 0}

```

where v is the value, LC is the left count.

And the output **F** would look like:

```
{v: Z, LC: 0, NR: Z}
     {v: G, LC: 0, NR: G}

```

where NR is a reference to it's parallel node in **T**. At this point, F has all the capitalized letters `[Z, G]` and we know the indexes of each.

Now lets see what happens if I insert `D` in-between `c` and `e`.

First, we know the index 3 at which this happens and can insert it into and rotate **T** accordingly. T will look like:

```
                        {v: D,LC: 3}
        {v: c,LC: 1}                    {v: f, LC: 1}
{v: Z, LC: 0}   {v: b, LC: 0}       {v: e, LC: 0}   {v: G, LC: 0}

```

Once **T** has been set, I can do a binary search and insert in **F**. I'd start at the root node `{v: Z, LC: 0, NR: Z}`, use the node reference to find the corresponding node in **T** and use the node in **T** to calculate the index in *O(log n)* time. I'd have to repeat this *O(log n)* times.
> 1 votes

# Answer
# An $O(\log n)$ solution for dynamically changing source list

## The problem

In a previous answer, I assumed that $S$ was a fixed list of elements, considered as a set ordered by the place of elements in the list. Only some property of the elements was supposed to be modifiable. The problem was to maintain another ordered list $F$ where elements of $S$, filtered for that property, could be inserted or removed, and such that the rank index of an element in $F$ was returned when the element was inserted.

Assuming the list to be fixed was essential because, by precomputing the rank index of each element in the list, if was possible to check the order of two elements in unit time $O(1)$ by comparing their ranks.

**In a later comment, the poster of the question indicated that in addition to the stated specification of the problem, the list $S$ itself can be modified by insertion and deletion.** Then there may no longer be a way to check the order of two elements in unit time. It is possible to maintain a rank index dynamically, as shown below, but computing it has a cost $O(\log|S|)$, so that the whole complexity of each operation is multiplied by that value, thus having a complexity $O(\log|F|\times\log|S|)$, or, to simplify in $O(\log^2 n)$ where $n=|S|$ is the size of the source list.

So I propose here a structure for implementing both lists $S$ and $F$ in such a way that:

* the order in $S$ is preserved for both,
* elements can be inserted or removed anywhere in $S$,
* any element of $S$ that is modified to satisfy a property $P\_F$ can be inserted in $F$, or removed if it no longer satisfies $P\_F$,
* for any element, it is possible to find its rank index in $S$ and in $F$
* all operations being executed with a cost $O(\log |S|)$.

Furthermore the technique can be extended to handle simultaneously several lists $F\_1, \ldots F\_i\ldots$ each corresponding to a different property $P\_i$.

Finally, I propose a technique to maintain a simple linked list of the elements in $F$, so that they can be listed in time $O(|F|)$ independently of the size of the source list $S$.

## The base structure

The idea is to use a unique self-balancing binary search tree (BST) such as an AVL tree or a red-black tree). This tree is first used to implement the list $S$. This may seem strange as there is no a priori order to the elements of the list, and their order is determined only by arbitrary insertions and deletions. So the insertion procedure has to be changed, in a fairly trivial way, as you choose to insert a new node after some given node of the existing structure (inducing the order as a consequence, since there is none a priori) and rebalance the tree accordingly.

To every node $N$, you add a weight $W\_S$ which is the number of elements of $S$ in the subtree rooted in $N$, actually the number of nodes of that subtree. This weight can be updated when inserting of deleting a node without changing the $O(\log |S|)$ cost of the operation. Furthermore, the weight can be used to compute the rank index of a node in $O(\log |S|)$ time, or to retrieve a node from its rank in the same time.

The rank index is computed on the fly by adding the weights of all the immediate siblings on the left of the path from the tree root to the concerned element of $S$. Their number is $O(\log |S|)$.

Conversely, it is easy to find in logn time an element of F from its (left to right) index by walking down from the root and leaving enough elements on the left.

## Implmenting the list $F$

To implement the list $F$, one simply marks as such the nodes of the tree that contain an element of $F$. Actually they can be simply identified by testing he property $P\_F$, when that test is cheap (i.e. at worst $O(1)$)

To be able to compute the index of an element in the list $F$, we add to each node $N$ a second weight $W\_F$, which is the number of elements of $F$ in the subtree rooted in $N$. This weight is updated exactly like the previous one $W\_S$. It is also used in the same way to get the index of a node in $F$ or to find a node in $F$ from its rank. There is a little subtlety in the latter, as, after leaving enough nodes on the left, we may have to search for the next subtree with a non zero weight $W\_F$, since that weight can be zero for some nodes.

All this can be achieved in time $O(\log|S|)$ for each operation.

**Enumerating $F$**

If you want to enumerate in order all the elements of the list $F$, this can be done by enumerating the elements of $S$ by walking the tree, and filtering out those that are not in $F$. That take time $O(|S|)$.

But, it may be the case that the list $S$ is much larger than $F$, and it would be convenient to enumerate easily the elements of $F$ without this overhead, in time $O(|F|)$.

This can be done by maintaining in each node a link $L\_F$, which is NIL if the node is not in $F$, or is the last node in $F$, and which points to the next node in $F$ when it is a node in $F$ other than the last one.

These pointers have to be maintained every time a node is inserted in $F$ or removed from it. But it is easily done in time $O(\log|S|)$ like other operations, thus not modifying the complexity. It is obviously possible since we can find the rank $r$ of a node $N$ inserted in $F$, and we can find the nodes preceeding and following $N$ from their rank $r-1$ and $r+1$, each in time $O(\log|S|)$. But there are faster ways to do it.

## Using several filtered lists

The means for implementing the filtered list $F$ are built on top of the self-balancing binary search tree representing the list $S$, but they interfere in no way with the operations on that tree concerning $S$. Thus it is possible to implement in the same way as many filtered lists as may be needed, corresponding to different filtering predicate.

**Note:** The above sketches the algorithmic technique. Writing the whole thing is pseudo-code is far beyond what could be considered reasonable in a normal answer.
> 1 votes

---
Tags: data-structures, linked-lists, lists, balanced-search-trees, ordering
---


# Question
Title: Proof by induction concerning approximation algorithm for subset sum
**Assignment question**

For algorithm APPROX-SUBSET-SUM, prove by induction on $i$ that for every element $y \in P\_i$ that is at most the target sum $T$, there is a $z \in L\_i$ such that

$$\frac{y}{(1+\frac{\epsilon}{2n})^i} \leq z \leq y$$

Here $\epsilon$ is the relative error bound, $P\_i$ is the set of all subset sums of the first $i$ elements in the universe, and $L\_i$ is the corresponding discretized set produced by APPROX-SUBSET-SUM.

**My thoughts**

I understand that *proof by induction* means that proving something for all natural numbers by first proving that it is true for $0$, and that if it is true for $n$ (or sometimes, for all numbers up to $n$), then it is true also for $n+1$. However, do I simply substitute $0$ and $n+1$ into $n$ and that would solve the question completely?

# Answer
> 1 votes
You haven't described the approximation algorithm, so I assume it's something like the following one (perhaps with a few changes in some details):

* Input: a universe $U = \\{x\_1,\ldots,x\_n\\}$, a target sum $T$, and an accuracy parameter $\epsilon$.
* Initialize $L\_i = \\{0\\}$.
* For $i = 1, \ldots, n$:
* + Compute $L\_{i+1} = L\_i \cup \\{\ell + x\_i : \ell \in L\_i\\}$.
* + Remove all element larger than $T$ from $L\_{i+1}$.
* + Replace each element $\ell \in L\_{i+1}$ by the largest power of $1+\epsilon/2n$ which is at most $\ell$.
* Return the element in $L\_n$ closest to $T$.

This is a $1+O(\epsilon)$-approximation algorithm, in the sense that it can tell whether there is a subset of $U$ summing to roughly $T$, up to a factor of $1+O(\epsilon)$.

The exercise asks you to show that for each $i \in \\{0,\ldots,n\\}$, the following is true: if $y \in P\_i$ (the set of all sums of subsets of $\\{x\_1,\ldots,x\_i\\}$) is at most $T$, then there is an element $z \in L\_i$ which is approximately equal to $y$, in the sense that $$ \frac{y}{(1+\frac{\epsilon}{2n})^i} \leq z \leq y. $$ Taking $i = n$ will give the desired analysis of the complete algorithm.

Let us denote the claim symbolically by $C\_i$. The exercise suggests that this claim can be proved by induction on $i$. This suggests the following plan to prove $C\_0,\ldots,C\_n$:

1. Prove $C\_0$.
2. For $i=1,\ldots,n$, assuming $C\_{i-1}$ is true, prove that $C\_i$ is true.

To find out what claim $C\_0$ or $C\_{i-1}$ is, you will need to substitute $0$ or $i-1$ for $i$ in the claim.

Good luck with executing this plan.

---
Tags: approximation, induction
---


title: Defining if a language is regular

text:
# Question
Title: Defining if a language is regular
$L\_4 = \\{ w | w \text{ does not contain symbol a immediately followed by symbol b} \\} $

where: $ \Sigma = \\{ a, b, c \\} $

So far I believe I have a defined regular grammar for this language, however I am having trouble coming up with an equivalent regular expression.

$\<Language\\\_4\> ::= a \<AOrC\> $

$\<Language\\\_4\> ::= b \<Language\\\_4\> $

$\<Language\\\_4\> ::= c \<Language\\\_4\> $

$\<Language\\\_4\> ::= \epsilon $

$\<AOrC\> ::= a \<Language\\\_4\> $

$\<AOrC\> ::= c \<Language\\\_4\> $

$\<AOrC\> ::= \epsilon $

Via a standard regex grammar this could be done via a lookahead, however I don't believe that the lookahead operation is a valid regular language operation. I'm having trouble proving that if it is true though.

This is for a homework assignment, so I'm not expecting a full answer just some pointers in the right direction.

## Edit

I went through this set of answers: How to convert finite automata to regular expressions?

I then used Arden's Lemma as it seemed the most straight-forward.

First I defined:

$Q\_0 = aQ\_1 \cup bQ\_0 \cup cQ\_0 \cup \epsilon $

$Q\_1 = cQ\_0 \cup aQ\_1 \cup \epsilon $

$ Q\_1 = cQ\_0 \cup aQ\_1 \cup \epsilon $

Apply Arden's Lemma:

$ U = a $, $ L = Q\_1 $, $ V = cQ\_0 $

Then I get:

$Q\_1 = a * c Q\_0 \cup \epsilon $

By then substituting $Q\_1$ into $Q\_0$ I get:

$Q\_0 = a\[a\*cQ\_0 \cup \epsilon\] \cup bQ\_0 \cup cQ\_0 \cup \epsilon $

$Q\_0 = \underbrace{(aa * ac \cup b \cup c)}\_U \underbrace{Q\_0}\_L \cup \underbrace{a \cup \epsilon }\_V $

$Q\_0 = (aa * ac \cup b \cup c)\* a$

Is this a correct application of the lemma?

## EDIT 2

I've tested the regex more and it doesn't match the desired language. I think there may be an error in my application of the lemma. I'm going to try the application again in case I missed something.

# Answer
Hint: Here are a few easier languages to practice on:

1. Every occurrence of the symbol $a$ is followed by a non-$a$ symbol. (Hint: every $a$ occurs in the context of $ab$ or $ac$.)
2. No occurrence of the symbol $a$ is followed by another $a$. (The only difference from 1 is that a word could end with $a$.)
3. Every occurrence of the symbol $a$ is followed by a non-$b$ symbol. (Hint: what are the possible contexts of $a$?)
4. Your language. (Combine the answers to 3 and 2.)
> 1 votes

---
Tags: regular-languages, regular-expressions
---


# Question
Title: Finding a minimum set of dependencies in a cycle-filled dependency graph
I have a graph of a large number of targets. Each target depends on a list of other targets. The graph is very large and filled with cycles of dependencies.

My goal is to find the smallest subset of targets that, if I remove all of their dependencies, breaks all of the cycles, leaving me with a buildable dependency tree.

This sounds very much like a well-understood graph problem to me, but I can't figure out which one. I'm afraid it also smells like an NP complete problem, but I'm hoping there's a good trick that I've missed. Can someone suggest what the name of this problem might be so that I can read a bit more about it, or what a good approach to solving it could be?

# Answer
> 1 votes
Decompose your graph into strongly connected components. Now each strongly-connected component (SCC) of size $\>1$ contains a cycle.

Let $G=(V,E)$ be the dag of SCCs obtained by this decomposition. Sometimes $G$ is called "the metagraph". Let $S \subseteq V$ be the set of SCCs of size $\>1$. Now our algorithmic problem is as follows:

> Given the dag $G$ and the set $S$, find a minimum-size set $T \subseteq V$ such that for every $v \in S$, there's a path from $v$ to some vertex of $T$.

The rest of the answer below is incorrect, but I'll leave the problem statement above in case it helps someone else find a clean algorithm.

---

This problem can be solved using a network flow algorithm.

In particular, this problem can in turn be rephrased as something akin to a minimum-cut problem: if we add a source vertex $s$ with an edge to each vertex of $S$ and a sink vertex $t$ with an edge from each vertex of $T$ to $t$, we want to find a minimum-size set of vertices that completely disconnect $s$ from $t$. Notice that this isn't quite the normal minimum-cut problem, because here we care about minimizing the number of selected vertices rather than minimizing the cost of the edges that cross the cut, but it's close.

Here's how we can solve this problem. For each vertex $v \in V$, we add two vertices $v\_\text{in},v\_\text{out}$, and we add an edge with cost 1 from $v\_\text{in}$ to $v\_\text{out}$. Also, we replace each edge $(v,w) \in E$, with the edge $(v\_\text{out}, w\_\text{in})$, and we make this edge have cost $\infty$. We add a source vertex $s$ and, for each $v \in S$, we add a source vertex $s$ and an edge of capacity $\infty$ from $s$ to $v\_\text{in}$. We also add a sink vertex $t$ and, for each $v \in V$, we add an edge of capacity $1$ from $v\_\text{out}$ to $t$. Let $G'=(V',E')$ be the resulting graph.

Finally, we find a minimum $(s,t)$-cut in $G'$. This can be done by using a standard network flow algorithm to compute the maximum $(s,t)$-flow, and then using the Ford-Fulkerson min-cut/max-flow theorem to reconstruct a minimum $(s,t)$-cut. Suppose the cut is $(U,V'\setminus U)$, where $s \in U$ and $t \notin U$. Then for each vertex $v \in V$ such that $v\_\text{in} \in U$ and $v\_\text{out} \notin U$, we add $v$ to $T$. This gives us a set $T$ of vertices that, in $G$, disconnect $s$ from $t$, and by construction, the size of $T$ is minimal.

# Answer
> 1 votes
I have some thoughts about complexity of this task. First of all let's rephrase original task:

> Given the graph $G=(V,E)$ with only 1 SCC, find the biggest subset of vertexes $R \subseteq V $ such that it forms DAG.

*In case when we have more that 1 SCC we can break original graph on subgraphs that contans only 1 SSC (as shown in answer above) and solve task for each subgraph independently.*

Let's call $t\_i$ - will we take vertex $i$ to resulting graph or not. Now we able to write some implications using $t\_i$, for example:

$$ t\_a \land t\_b \to \overline{t\_d}\hspace{10pt}(1)\\ t\_a \land t\_c \to \overline{t\_d}\hspace{10pt}(2)\\ ... $$

$(1)$ means if we will take to result graph vertexes $A, B$ we can not take vertex $D$. And, of course, we can have more such implications.

We can rewrite each implication in another form: $$ t\_{i\_1} \land t\_{i\_2} \land ... \land t\_{i\_{n-1}} \to \overline{t\_{i\_n}}\\ \overline{t\_{i\_1} \land t\_{i\_2} \land ... \land t\_{i\_{n-1}}} \lor \overline{t\_{i\_n}}\\ \overline{t\_{i\_1}} \lor \overline{t\_{i\_2}} \lor ... \lor \overline{t\_{i\_{n-1}}} \lor \overline{t\_{i\_n}}\\ $$

And here we have Boolean satisfiability problem that can be solved in $linear$ time iff implication is of form $a \to b$ (e.g. only 2 variables in equation, it's called 2-SAT problem). In case when more that 2 variables are used in equations it is NP-complete.

---
Tags: graphs, reference-request, optimization
---


# Question
Title: Difference between SRSW and MRSW safe Boolean registers
I'm reading The Art of Multiprocessor Programming and am currently trying to understand Chapter 4 — The Foundations of Shared Memory.

In section 4.2 it is shown how to build a multi-reader, single-writer (MRSW) safe Boolean register from a single-reader, single-writer (SRSW) safe Boolean register. So, the only difference is that the new register supports multiple readers, but the consistency guarantee (safe) is the same.

The implementation (figure 4.6) uses an array of SRSW safe Boolean registers, with one element for each reader. What I don't understand is why can't we treat a SRSW safe Boolean register as a MRSW safe Boolean register, already?

The definition for the **safe** consistency level says that a register is safe if:

1. A *read* call that does not overlap a *write* call must return the value written by the most recent *write* call.
2. A *read* call that overlaps a *write* may return any value within the register's allowed range of values (in the case of a Boolean register, just 0 and 1).

It seems to me that a SRSW safe Boolean register can already be treated like a MRSW safe Boolean register because any number of reads concurrent with a write will return either 0 or 1. Non-overlapping reads are obviously fine.

Is there a nuance I'm missing here or is it just a self-imposed limitation that a SRSW safe Boolean register can't be used with multiple readers, just by the definition? I understand this whole register derivation tower is pretty artificial and used mostly for theoretical considerations, so I'm thinking such an artificial limitation is very possible.

# Answer
You do not know anything about the behavior of the register if read calls overlap.

Perhaps the register is a sensitive electrical component and overlapping reads will blow it up?

Perhaps reading (counter-intuitively) requires changing the state of the register, for instance writing the target memory location which the value must be read in to? If two reads overlap then it might end up writing the value to the wrong location or to only one of the two locations?
> 3 votes

---
Tags: concurrency, shared-memory
---


# Question
Title: How can there be undecidable languages in P/1?
I didn't understand some things about $ P/POLY$ class, and I will be thankful if you could help me. as I learned in class,

a turing machine M accepts language L with advice $ {a\_n} $ if

$\qquad\displaystyle M(x, a\_{|x|} ) = 1 \iff x \in L$.

1. Does it mean that M with the advice **decides** L (halts on every input)? or **recognizes** L? (accept every x in L but may not halt on x that is not in L)

Generally, if a language L is in P it means that there is polynomial time machine that **decides** it right? I feel like it really confused me.

then we defined: $ P/POLY $ = union of (DTIME($n^{k\_1}), n^{k\_2})$ on every $k\_1,k\_2$ in $N$ .

we proved in class that there is a unary language which is **undecidable**, and that every unary language is in $P/1$. that means that there is language in $P/1$ which is undecidable.

2. I don't understand it because $P/1$ is in $ P/POLY $ . as I understand by the definition, there is poly time machine that **decides** it.. so what do I get wrong?

# Answer
> 7 votes
if $L\in P/poly$ then there is a machine that **decides** any input $x$, *given the advice $a\_{|x|}$*.

However, if the advice is not given, maybe no machine can decide $L$. This is what happens in the unary case. Note that the machine doesn't know the advice *and **cannot** compute it*, i.e., the set of advices (for a specific $L$) may be an undecidable language.

On the other hand, if someone gives you this (possibly undecidable) set, you have more power at hands. Similarly, if you can compute this set (for a certain $L$), say get $a\_n$ in $f(n)$ time, then $L$ clearly belongs to $DTIME(poly(f(n)))$.

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