# Question
Title: How to calculate or estimate how long it takes to solve a recurrence relation?
I am trying to understand how to solve complex recurrence relations and whether there is a general method or technique to help me. That being said I am not talking about recurrence relations that can be solved using the (generalized) *Master Theorem* or the *Akra–Bazzi* method.

This is by no means a "I have some homework to solve, please solve it for me" question. It is more at a conceptual level. I want to be able to solve and "see" through these relations with ease.

**How do you efficiently calculate the time needed to solve a recurrence relation?**

Is it something that, simply put, takes experience and personal intuition? Is there some cannon method that I am not aware of? Moreover, how do you go on to calculate the same relations for cases where you have *memoization*?

# Answer
There are at least three questions here:

1. How does one solve a recurrence relation on paper?
2. How does one efficiently calculate a sequence given by a recurrence relation, say using memoization?
3. Given a recurrence relation, can one predict the running time of the best method for computing it?

Let me answer them one by one. For the first question, this is a particular instance of the classical question, how to solve problems. Consider the (finite!) recurrence relation given by $$ \gamma\_0 = 1, \quad \gamma\_{m+1} = E, \quad \ell\gamma\_{\ell+1} = (2\ell-m+c-1)\gamma\_\ell + (m-\ell+1)\gamma\_{\ell-1} (1 \leq \ell \leq m). $$ (The sequence is $\gamma\_0,\ldots,\gamma\_{m+1}$, and $E,c$ are parameters.) What is the solution of this recurrence? If you're interested, have a look at the top of page 7 in this paper, which unfortunately doesn't explain how the authors found the explicit formula; Mathematica manages to solve this recurrence somehow. For some general methods useful for solving recurrence relations, consult our reference question.

For the second question, we can consider a very general class of recurrence relations which produce a sequence $(\gamma\_i)\_{i \in \mathbb{N}}$ by giving each $\gamma\_i$ in terms of values $\gamma\_j$ for $j \< i$. Such recurrences can be efficiently computed using memoization. The time required to compute $\gamma\_n$ is upper-bounded by $n$ multiplied the time it takes to calculate the defining formula of $\gamma\_i$. This bound can be tricky to evaluate, since the time needed to carry arithmetic operations depends on the size of the operands, which could grow rather fast depending on the recurrence (consider for example $\gamma\_0 = 1$, $\gamma\_n = n\gamma\_{n-1}$).

For the third question, it is easy to artificially reduce the halting problem to my statement of the problem, so in general it is hard to predict the *best* running time. But one can probably predict (or at least upper-bound) the running time of memoization. Given my answer to the previous question, all you need is to somehow bound the size of the elements of the sequence. In many cases one can get reasonable bounds, for example this is probably possible for recurrence relations in which $\gamma\_n$ depends polynomially on $n$ and $\gamma\_{n-1},\ldots,\gamma\_{n-c}$ for some finite $c$. While you shouldn't expect to get tight bounds this way, for a "generic" recurrence relations, one can probably predict the order of growth.
> 5 votes

# Answer
There is no general way to solve all recurrence relations, however, there is a general way to solve all homogeneous linear recurrence relations exactly by employing linear algebra.

The idea is as follows: 1) For a linear recurrence relation of size $k$, e.g. $a\_n = c\_1 a\_{n-1} + c\_2 a\_{n-2} + ... + c\_k a\_{n-k}$, write down $k$ consecutive iterations from $n-k$ to $n$.

2) Transform the set of $k$ equations into a matrix-vector form of dimension $k$. The $n$-steps of the addition of the linear recurrence combined with the $k$-dimensional vector of initial values will become a recurrence of an $n$-step $k \times k$-dimensional matrix multiplication followed by one last matrix-vector multiplication on the right side with the initial vector.

3) rewrite the $n$-step matrix multiplication of $A$ into $A^n$

4) diagonalize the matrix $A$ into three matrices: $A = TDT^{-1}$ of which $D$ is a diagonal matrix and $T$ is regular. In some corner cases, $A$ might not have a diagonalized form, in which case one should attempt to find the (more general) Jordan normal form of $A$ instead. 4.1) This means one need to find all eigenvalues $\Lambda$ and their corresponding eigenvectors $V$ of $A$. 4.1.1) One need to find all roots of the characteristic polynomial of $A$ to get its eigenvectors and corresponding eigenvalues.

Note that $D$ can easily be expressed in a closed form depending on $A$'s eigenvalues $\lambda\_1 ... \lambda\_k$, and both of $T$ and $T^{-1}$ can easily be expressed in a closed form depending on its eigenvectors $v\_1 ... v\_k$. At this point I would recommend to drop the parameters $c\_1 ... c\_k$ from the equation and abstract them away using the above $\Lambda\_i$ and $v\_i$ for readability.

5) now rewrite $A^n$ into $(TDT^{-1})^n = T D^n T^-1$. Note that $D^n$ can easily be computed from $D$, since it is diagonal.

6) figure out an easy way to formally multiply this equation out. I recommend leaving the vector of initial values out until the very end. When finally computing $A^n * b$, note that one only need the last row of the resulting product, meaning one can leave out all others.

7) Depending on what one intend to do with the recurrence relation, it may be time to substitue $c\_1 ... c\_k$ back into the eigenvalues and eigenvectors.

8) The resulting equation gives $a\_n$ explicitly depending only on the initial values $a\_0, a\_1 ... a\_{k-1}$ and either $c\_1, c\_2 ... c\_k$ or $\lambda\_1 ... \lambda\_k$ and $v\_1 ... v\_k$.

These results can be generalized for linear recurrences with affine components of n added (functions depending only on n), and even further for small polynomial, exponential and some other components depending only on n. However, it's not possible to generalize this explicit closed formula for linear recurrences for arbitrary functions depending only on n, because doing so would require a closed explicit form for arbitrary series given its sequence function, and AFAIK that's impossible.

As soon as recurrences with more than one operand are generalized from linear to polynomial recurrences, things become very complicated. Even if we allow only quadratic recurrences of a *single* step, things are already complicated and there are almost no non-trivial exact solutions (only a countable infinite subset out of the uncountable infinite parameter space actually do have closed forms). One neat example is $a\_n = 2\*a\_{n-1}^2 - 1 = \cos(2^n \arccos(a\_0))$, which comes from the double angle cosine law. Generally, for finding one of those sparse explicit solutions to general polynomial recurrence relations, one have to consider Fourier theory and keep track of repetitions, which can be done using functional properties of trigonometric or polynomials of exponential functions.

If one generalize even further, all bets are off. If you need a numerical result of one of those hard cases, the best thing one can do is trying to guess some upper and lower bound, which is usually done by ignoring all but the most significant parts of any term.

Also, recurrence relations are closely related to generating functions.

This is a subject where one can talk more than this site can take.
> 3 votes

---
Tags: recurrence-relation
---


# Question
Title: minimum vertex set removal for edge-free graph
I'd like to know the name and the algorithm for the following problem which I'm guessing is a classic, but is slightly different from graph connectivity.

Consider a undirected graph G=(V,E). What is the minimum number of vertices which removal (vertices and their adjacent edges) makes the resulting sub-graph empty of *any* edge?

For example: If A - B - C, then just need to remove B. If A - B - C and A - C, then need to remove at two vertices (any pair).

For an algo, intuitively I'd proceed by removing first the vertex of highest degree and proceed the same on the remaining graph until there are no edges. Not sure if it gives the min number. For sure, in the worst case I can always go through all possible |V|! removal possibilities and take the min.

# Answer
> 5 votes
The problem you describe is called minimum vertex cover. It is a well-known NP-complete problem, so there is no known algorithm that will always be fast (as in polynomial runtime) and give the optimal solution. However, fast approximation solutions are known, as well as algorithms that, while slow in the worst case on general graphs, are fast on significant classes of graphs. See the linked Wikipedia article for details and links to even more details.

---
Tags: terminology, graphs
---


# Question
Title: How does one efficiently produce all binary sequences with an equal number of 0's and 1's?
A *binary sequence* of length $n$ is just an ordered sequence $x\_1,\ldots,x\_n$ so that each $x\_j$ is either $0$ or $1$. In order to generate all such binary sequences, one can use the obvious binary tree structure in the following way: the root is "empty", but each left child corresponds to the addition of $0$ to the existing string and each right child to a $1$. Now, each binary sequence is simply a path of length $n+1$ starting at the root and terminating at a leaf.

Here's my question:

> Can we do better if we only want to generate all binary strings of length $2n$ which have precisely $n$ zeros and $n$ ones?

By "can we do better", I mean we should have lower complexity than the silly algorithm which first builds the entire tree above and then tries to find those paths with an equal number of "left" and "right" edges.

# Answer
Obviously there are $4^{n}$ binary strings of length $2n$. To traverse the binary an algorithm has to visit each node once, i. e. it has to do $$ \sum\_{i=0}^{2n} 2^i = 2^{2n+1} - 1 = \mathcal{O}(4^n)$$ steps.

Let's consider a recursive algorithm which traverses the tree you described, but counts the number of ones and zeros on its way, i. e. it will only traverse the good part of the tree.
But how many such binary strings with $n$ 0's and $n$ 1's are there? We choose $n$ 1's for our strings of length $2n$ and use Stirling's formula in step 2: $$ {2n \choose n} = \frac{(2n)!}{(n!)^2} = \frac{4^n}{\sqrt{\pi n}} (1 + \mathcal{O}(1/n))$$

**EDIT**
Thanks to Peter Shor's comments we can also analyse the number of steps needed by the second algorithm, which counts the 1's and 0's. I'm citing his comment from below:

> We want to find all binary sequences with exactly $n$ 0's and $n$ 1's. We traverse the binary tree where each node is a sequence of at most $2n$ 0's and 1's. We don't need to visit any node with more than $n$ 0's or more than $n$ 1's. how many nodes do we need to visit? There are ${i+j \choose i}$ strings with $i$ 0's and $j$ 1's. Summing this over all $i,j \leq n$ gives $\sum\_{i=0}^n \sum\_{j=0}^n {i+j \choose i} = {2n+2 \choose n+1} − 1$. Now, we need to visit each of these nodes at a constant average cost per node. We can do this by visiting each left child first, and each right child second.

Using Stirling's formula again we obtain $$ {2n + 2 \choose n + 1} - 1 = 4^{n+1} \frac{1}{\sqrt{n+1}} (1 + \mathcal{O}(1/n)) - 1 = \mathcal{O}(\frac{4^n}{\sqrt{n}}) $$ as the running time of the new algorithm.
> 6 votes

# Answer
Perhaps I'm being thick, but the original question asked for a way to generate all "balanced" binary sequences of length 2n that was more efficient than traversing a tree of *all* binary sequences of length 2n and outputting only those which were balanced. So why use a tree at all?

Here's pseudocode for a recursive algorithm that generates all such sequences (the keyword "yield" sends a sequence to the output):

```
function all-balanced(n) {
  all-specified( "", n, n );
};

function all-specified( currentString, zeroes, ones ) {

  if (zeroes == 0) {
    for i = 0 to ones {
      currentString += "1";
    };
    yield currentString;
    return;
  };

  if (ones == 0) {
    for i = 0 to zeroes {
      currentString += "0";
    };
    yield currentString;
    return;
  };

  all-specified( currentString+"0", zeroes-1, ones );
  all-specified( currentString+"1", zeroes, ones-1 );
  return;
};

```

If I'm misunderstanding something, please tell me, but it seems to me that this is about the most efficient answer to the problem actually posed, which never specified the use of a tree.
> 3 votes

---
Tags: algorithms, graphs, binary-trees
---


# Question
Title: Scheduling Algorithm for aperiodic multiprocessor tasks
I've got a System, which is defined as follows:

* A limited number of stations is given (n), which can offer different services (for now there are two services). A station can either offer one of the services or both (maybe it will be extended one day, then it should work with x different services and a station can offer 1..x of these services).
* The throughput for a service can differ from station to station.
* Each service in the system can have a fixed priority assigned by the developer. If multiple services have to be scheduled and the scheduler isn't able to assign each service at once to a single station, it can split up the services and chose the service with the highest priority to run first and run the other service/s later on. (also see next point)
* If a task requests multiple services, it is okay to split them up. For example, there are two services requested (a and b): requested service a is running on station c for 10 minutes, afterwords it is moving to station d to receive service b. However, you could also think of this as two separate tasks, each of which requests a single service, if you prefer.
* A task can arrive at any time, for example the incoming of a new request.
* Each task has an arrival time, an execution time (computed by the requested amount of the service and the amount a station can offer. in other words: this is the time, a particular station will need to complete a task) and a deadline
* Different tasks have different execution times.
* Arrival time: there are "reservations", then the arrival time is known before the task arrives. but there are other cases, in which the arrival time is not known, so the arrival time equals "now".
* A station can serve one task at a time, but a task can request multiple services at once (there are stations which offer these services at the same time, the different services doesn't influence each other).
* Tasks can be preempted and moved between stations during execution, meaning that if one task is running on a station the task can be assigned to a different station which offers the same service (this station-change can cause costs, based on the distance between different stations). This could be caused by another task which needs the station the first task was running on until now.
* The algorithm has to work in real time.

The System is given and works already with one service, I have to adapt it to work with multiple services. For this, I have to look for and implement a new scheduling algorithm, but I have no idea for what I have to look for. Another possibility is to design my own algorithm, but due to the lack of knowledge in this sector I think it would be a bad idea.

Any hints for what kind of scheduling algorithms I have to look for?

# Answer
> 1 votes
One technical term that might help you focus a literature search is "load balancing". See, e.g.,

---
Tags: algorithms, scheduling
---


# Question
Title: How to show that this algorithm for evaluating polynomials works?
I'm having trouble showing how to solve this problem in particular the part where it asks "To Show that the following pseudo-code fragment finds the value of the polynomial..."

How do I exactly show that? I don't understand what that would entail and my professor isn't exactly that helpful he says to prove it for all $n$, but I don't understand how to show that mathematically through programming. He says not just to give a particular example, but rather show it works for all polynomials.

The whole question is this:

> It is required to find the value of the polynomial $$P(x)=\displaystyle\sum\_{k=0}^n a\_k x^k$$
>
> Show that the following pseudo-code fragment finds the value of the polynomial, given the coefficients $a\_0,a\_1,a\_2,...a\_n$ for a value of $x$.
>
> ```
> y = 0;
> i = n;
> while (i >= 0) {
>    y = a[i] + x * y;
>    i = i - 1;
> }
>
> ```

# Answer
> 1 votes
I suggest you use proof by induction, on the number of iterations of the loop.

In particular, find a loop invariant: an equation that relates the value of `y`, `i`, and $a\_0,a\_1,\dots,a\_n$, and that always holds each time you reach the head of the loop.

Then, prove that your loop invariant is indeed an invariant, using proof by induction.

# Answer
> 0 votes
This algorithm to compute the value of a polynomial is known as Horner's method. It is a more efficient way to evaluate a polynomial $p(x)$, in the sense that it takes fewer operations than the naive implementation.

Suppose, for example, you have a polynomial $$ p(x) = a\_0 + a\_1x + a\_2x^2 + a\_3x^3 $$ You could compute this in the obvious way, or you could rearrange it as $$ p(x) = a\_0 + x(a\_1 + x(a\_2 + x(a\_3))) $$ and work from the inside out, keeping track of the values as you go, like this: $$\begin{align} y &= 0\\ y &= a\_3 + x \cdot y = a\_3 + x\cdot 0 = a\_3 \\ y &= a\_2 + x\cdot y = a\_2 + x(a\_3) \\ y &= a\_1 + x\cdot y = a\_1 + x\cdot (a\_2 + xa\_3)= a\_1+xa\_2+x^2a\_3\\ y &= a\_0 + x\cdot y = a\_0 + x(a\_1+xa\_2x+x^2a\_3x) = a\_0 + xa\_1 + x^2a\_2+x\_3a\_3 \end{align}$$ and you're done: you've evaluated $p(x)$ using fewer multiplications than you'd use in a naive evaluation (three versus five, in this case). In some applications, this might make a significant difference in running time.

To prove that this works for all polynomials, you could do an induction proof on the degree of the polynomial: show that this evaluates any 0-degree polynomial, and then inductively show that if it works correctly on a degree-$n$ polynomial, it will work correctly on a degree-$(n+1)$ polynomial.

---
Tags: algorithms, algorithm-analysis, correctness-proof
---


# Question
Title: Why is the processor's pipeline delay calculated as N*max(Delay) ? why not N*(D1 + D2 + D3 ... )?
Consider a four stage pipeline, and each stage has delays D1, D2, D3 and D4, so the total delay because of the various stages should be `N * (D1 + D2 + D3 + D4)` where N is the number of instructions, but I see that this is not the case, I see here that the delay is calculated as `N*max(D1,D2,D3,D4)` , why is only the max value taken into account ?

I try to apply the above two ideas for the below chart and none of them work.

For the below chart consider that the numbers on top are the time and the S1, S2, S3 and S4 denote the time spent any stage of an instruction on the pipeline

```
with N*(max(S1,S2,S3,S4)) = 4*(4) = 16,
and with N*(S1 + S2 + S3 + S4) = 4*(1+2+4+1) = 32

1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
S1 S2 S2 S3 S3 S3 S3 S4
   S1    S2 S2       S3 S3 S3 S3 S4
      S1       S2 S2             S3 S3 S3 S3 S4
         S1          S2 S2                   S3 S3 S3 S3 S4

```

# Answer
> 4 votes
Each stage of the pipeline is only as fast as the slowest stage. The calculation for the latency expresses this by taking the maximum delay (`max(D1, D2, D3, D4)`) and multiplying it by `N`, which is the number of stages. Thus: `N*max(D1, D2, D3, D4)`.

Keep in mind, `N` is the number of *stages*, not instructions. The formula measures the *latency*, not the total run time.

Your chart demonstrates this, as you can see that there is more and more delay building up in the first and second stages as they finish faster than the next stage. But there is a problem: where does the data from each stage go before it enters the next stage? The simple answer is nowhere: it is stuck in the current stage until the next stage is free. Your third stage is creating a traffic jam!

Consider this chart, in which each stage has been slowed down to take 4 time units (the `n` represents that processing is done but the data must wait for the next stage to clear):

```
    1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
    S1 n  n  n  S2 S2 n  n  S3 S3 S3 S3 S4 n  n  n  Done!
                S1 n  n  n  S2 S2 n  n  S3 S3 S3 S3 S4 n  n  n  Done!
                            S1 n  n  n  S2 S2 n  n  S3 S3 S3 S3 S4 n  n  n  Done!
                                        S1 n  n  n  S2 S2 n  n  S3 S3 S3 S3 S4 n  n  n  Done!

```

Here we can see that it takes each individual instruction 16 time units to make it through the pipeline (4 stages * max delay of 4). The total run time is only 28 time units. It takes 16 units for the first instruction to run, and 4 more time units for each additional instruction. So the run time formula is something like: `N*max(D1, D2, D3, D4) + (IC - 1) * max(D1, D2, D3, D4)` where `N` is the number of stages and `IC` is the number of instructions.

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


# Question
Title: How can I teach computer science without using computers?
In some places in the world, people don't usually have access to (and hence little knowledge of) computers, and even if they have, hard- and software are outdated and usage plagued by power outages and such. Access to (good) books also tends to be lacking. How can I teach computer science under such circumstances?

I'm worried that without being able to do experiments and apply what they learn, they won't learn (well) at all even though they are incredibly motivated and devote most of their time to this hobby. Is it possible to teach CS only theoretically?

# Answer
> 24 votes
Asking how you can study computer science without computers is a bit like asking how you can study cosmology without telescopes. Sure, it's nice to be able to look at the things you're studying and it's often very helpful to be able to play around with things. But there's a whole lot you can do without access to a computer: *in extremis*, you could probably do almost all of a undergrad course with no computers.

In practical terms, access to computers helps reinforce a lot of what you learn in a computer science course. Programming courses are, obviously, much more natural with access to a computer. On the other hand, being forced to write code on paper does encourage people to think about their code and make sure it really works, rather than just running it through a compiler again and again until it compiles and then running trivial test cases again and again until the obvious bugs go away.

Topics that would be most natural without computers would be the more mathematical ones. All the background mathematics, such as combinatorics and probability. Computability, formal languages, logic, complexity theory, algorithm design and analysis, information and coding theory. Anything to do with quantum computation!

# Answer
> 10 votes
There is the obvious use of paper and pencil. When I was taught signal processing the special signal processor was not directly available to us and we just handed in paper reports.

Note that the great computer scientist Dijkstra apparently did not use computers very much:

> Almost all articles in this series appearing after 1972 are hand-written. Having invented much of the technology of software, Dijkstra eschewed the use of computers in his own work for many decades. Even after he succumbed to his UT colleagues’ encouragement and acquired a Macintosh computer, he used it only for e-mail and for browsing the World Wide Web.

Cited from Disjkstra's Memorial

This shows that you can do great computer science without a computer!

Besides paper and pencil computer science problems can also be solved 'in the real world', e.g., demonstration of sorting algorithms with cards or - more unusual - with dance as done by the Sapientia University.

# Answer
> 8 votes
Many computer science theories are purely theoretical and can be solved using pen(cil) and paper. Getting information about them and communicating them to the outside world requires a computer.

# Answer
> 7 votes
See http://csunplugged.org/ for some great ideas. Google is one of the sponsors.

From the site:

> CS Unplugged is a collection of free learning activities that teach Computer Science through engaging games and puzzles that use cards, string, crayons and lots of running around.
>
> The activities introduce students to underlying concepts such as binary numbers, algorithms and data compression, separated from the distractions and technical details we usually see with computers.
>
> CS Unplugged is suitable for people of all ages, from elementary school to seniors, and from many countries and backgrounds. Unplugged has been used around the world for over twenty years, in classrooms, science centers, homes, and even for holiday events in a park!

# Answer
> 3 votes
You can, it's pretty obvious how you would do it. I'm not sure how useful it'd be to people, but you can.

But I don't even know how a would be teacher of computer science, can ask how you can teach computer science without a computer.

Because if you can teach computer science, then you would know how.

If you know that-

```
-Algorithms can be written on pen and paper, and traced on pen and paper.
-Flow charts are written on paper.

```

Studying normalization, the structure of tables of data for databases, can be done on pen and paper. (I only did that on pen and paper when I studied relational databases)

Computer science textbooks don't require a computer.

If you ever picked up a computer science textbook and studied it in a library you'd know you didn't need a computer to understand it.

But you should be aware that anybody that has sat in a computer science class can see that most people cannot program, it's just beyond them. Too abstract for people. That is even true at University level.

http://www.eis.mdx.ac.uk/research/PhDArea/saeed/paper1.pdf

> A substantial minority of students fails in every introductory programming course in every UK university. Despite heroic academic effort, the proportion has increased rather than decreased over the years. Despite a great deal of research into teaching methods and student responses, we have no idea of the cause.

I would add that to call it a substantial minority, is an understatement. It's a small minority that -can- program.

I would note though, the cause of the decline that he witnessed.. As computers got more popular e.g. between 2000 and 2010 (he wrote that in the middle of that decade), more wollies were interested in studying 'computer science'. Before then, only the more fanatical people were interested. And earlier on, using computers was more technical, but as computers got easier for the average person to use, and more powerful in the applications they could run, then more wollies were using them and more people that were only interested in what they could do rather than how they do it and how to do it.

# Answer
> 2 votes
It WOULD be possible to teach the concepts of Computer Science without a computer. Of course without access to a computer, what good does learning Computer Science really do?

When I was learning Computer Science in high school, our first several classes didn't involve computers at all. Instead, we worked from a book called Karel++, which taught object oriented concepts. The made up language can be "run" on a whiteboard or blackboard pretty easily because all of the code takes actions on a graph. Our first few assignments were all handwritten and the professor would demonstrate the correct solution on the board at the start of the next class.

When we started discussing algorithms, our professor called us all up to the front of the room and told us to stand in a line. He proceeded to demonstrate a few different sorting algorithms - starting with something silly he called "monkey sort" where he would randomly exchanged two of us and then check to see if we were sorted every iteration, but then performing bubble sort and shell sort \- by "running" them on us.

He drew diagrams on the board, explaining the basics of how computer memory and the stack work. He demonstrated variables and pointers (it was a C++ class) and from there to linked lists and trees...

I could probably add to this if I went over the notes I kept from that class, but that's all I remember now. If these suggestions are interesting, I can expand on this answer.

# Answer
> 2 votes
I did a computer science degree and thought we were taught much programming (in various languages) we also were taught many mathematical aspects (and some hardware too).

The maths parts were more important to the first year - think matrix mathematics which is essential to 3d graphics (how do you calculate a surface normal for lighting a vertex?). We did a lot of statistics - think job throughput analysis, what rate of jobs can you pass into a system before it clogs up? That's pretty important for many centralised systems, and networking.

You can teach many algorithms, one poster here mentioned giving students a number each and then getting them to sort themselves using various algorithms (that's active and informational). In fact, any algorithm that can be described in an animated image on the internet can be taught in this way. Similarly the fundamentals of computing - program counter, accumulator and registers can be taught in the same way, or on paper. How about student-based multithreading - set a group of students a card game with a stack between each of them in a classic multi-threading exercise (or the 1 shared spoon problem). Or design patterns, I can think the blackboard architecture is perfect for students to learn how multi-process communication can be implemented, or a n-tier architecture described as a sort of chinese-whispers game or finite-state machines would suit students acting as modules in a 'living computer'. You could teach binary maths, or stack-based (ie reverse polish) execution.

Of course if you have access to electronics you could build an analog computer out of op-amps. They're cool.

Unfortunately all this will seem more like maths than computing, but much of it will stick and one day they'll understand why they were taught it (assuming they go into the computing industry). Remember that anything a computer can do, a person can do - it'll just take him a *lot* more time and boredom to achieve the same result. You just have to take simple examples to demonstrate what the computer would do, and imagination to describe computing fundamentals in a less dry way that I was taught, way back :)

# Answer
> 1 votes
> Asking how you can study computer science without computers is a bit like asking how you can study cosmology without telescopes.

I am mostly answering just to react to this statement and because I strongly disagree with other answers. The correct comparison would in my opinion be

> Asking how you can study computer science without computers is a bit like asking how you can study cosmology **without a cosmos**.

Computer Science is *about* computers, not just using them. True, a lot of Computer Science is based on mathematics, so the mathematical parts can be studied without computers (thus you're teaching mathematics then) just like instead of cosmology you can study physics which will be useful once there is a cosmos (or have access to telescopes), but in the end what you're studying is still physics.

Now, what everybody is doing in the answers here is note how bachelor level computer science is mostly theoretical and doesn't require computers, the thing those people are IMHO forgetting is that the same people have used computers extensively up to that point. Without a natural understanding directly delving into the theoretical stuff will just cause many students to either give up or have a terribly mismatched view of computer science. So teach some programming, understanding of what computers are first and only afterwards get into the theoretical stuff.

> Like if I'm teaching students in Africa that have no knowledge of a computer besides general-level know-how but who aspire to learn advanced computer science and devote most of their time to this hobby?

Depends on budget:

* **Nearly no budget** If you've the money to travel to Africa grab a bunch of arduino clones (there are functional arduino clones for $13, check this list for example) , some output components (such as LEDs) and one laptop. Start with some basic programming, teach it to them on paper and have to input it on the laptop. It's not the most efficient way, but it will teach them at least a basic basic understanding of what computers practically are.
* **Low budget** Buy \\$750 dollars worth of \\$50 android smartphones and keyboards (microusb keyboards or bluetooth keyboards, check ebay.com or aliexpress.com for both the smartphones and keyboards). Yes they are crappy in a million ways, don't even tell me about it. Still though, you can input data on them (though don't even consider using the onscreen keyboards) and there are simple coding apps for android. Have multiple students per smartphone and that can work quite well.

So let me be clear, I am not saying Computer Science can't be taught without computers, just that you need to be used to computers and know them fairly well before you should start considering such a thing.

# Answer
> 1 votes
Computer Science is about algorithms and not (strictly) about computers (and electronics).

As such, study of algorithms (even of elementary arithmetic) can bring about understanding of computer science and programming. Remember that even term "algorithm" is a paraphrase of the author of an arithmetica book (al-Khwārizmī, circa 9th cent. CE).

Study of algorithms can be done using elementary means, but should provide coverage of why the algorithm works, how it came about and how can one actually demonstrate that it works correctly.

Thwe history behind the evolution of computer science and algorithms and programming is not to be underestimated. For example, Babbage's/Ada's calculator, Enigma machine, Konrad Zuse's plankalkul, ENIAC etc.

Then one can introduce programming (and programming languages) as a way to formalize algorithms. This can also be done (to a large extend) using elementary means.

**Note**, some studies have shown that peole learning programming have two main difficulties in understanding (related to the overloading of symbols for example asignment vs equality test and the operation of a RAM machine).

1. Loop constructs (e.g for, while etc..) seems difficult
2. Assignment vs equality testing, seems also difficult.

So one can make sure these are clearly grasped and understood by the people.

Moreover if any computer can be accessed (even a calculator which can be programmed), this can be used to provide application examples and hands-on experience. Else one can use a simulated computer. This can be done in various ways, for example a group of people can simulate parts of a computer and the class can design algorithms to solve various problems for this simulated computer and see how it goes. This can be seen as a game also, be creative and make-do.

Then some (abstract) computation models (for example Turing Machines) can be introduced and related to the previous material on algorithms and the formalisatinn into a (programming) language.

If one wants to introduce the electronics of an actual computer this can be done also in two parts.

Remember that even in universities some electronics and computer architecture courses are theoretical (one does not actually come into contact with a CPU or design one).

So some principles of operation of electronics (and the underlying physics) related to computer architecture can be introduced (semiconductors, solid-state energy zones, p-np gates, etc.).

Then one can leverage the previous material about programming and algorithms and introduce (modern) techniques of CPU design (and description) which are used in the industry (Logic gates, Flip-Flops, FPGA, VHDL, CMOS circuits etc).

This can be taken further into, CPU design architecture issues like parallelism, pipelining, cache memory, vector adressing, micro-programming, DMA, etc..

Well, ok maybe this can be too much, but added for making the answer self-contained.

# Answer
> -1 votes
Are you looking to teach programming?

When I was a kid, we went on a camping holiday and I took the computer manual with me. I was able to write a simple game using pen and paper.

This was my first real program I guess, so a lot of learning was involved. I knew what I wanted to do, but there were a lot of false starts while I figured it out. But eventually I was able to write out the whole code.

I guess what I'm saying is start with pseudo code and\or flow charts to plan the project and then translate into code. I was able to debug a lot of my code just by reading it. You could also use peer reviews here.

# Answer
> -2 votes
To echo to the previous answers: there is a lot to be learned just from reading and doing pen and paper exercises. If you can work the problem on paper you have the hard part down pat. However, I also wish to mention the existence of fairly cheap ways to expose students to CS. Are you familiar with the Raspberry Pi Project? Even if several people has to share or you can only afford to get 1 or 2 units it might still be worth considering as a way to expose your students to the technology.

# Answer
> -3 votes
am going to try wiggle on this one a little & "think outside the box". full blown computers are indeed expensive, sometimes resource-demanding and tricky to maintain. but there are many inexpensive electronic systems that mimic full-blown computers eg with LCD screens etc and which many basic programming principles can be applied, many battery powered. there is also a close connection of EE principles with computing such as building binary logic circuits etc.; also nowadays some toys have programmability capabilities.

* programmable calculators. some have entire programming languages (not so high level but more like assembly languages) built into them. some would support advanced programs.
* Raspberry pi minicomputer/microcontroller was developed for this purpose & runs linux. less than $40 in many cases.
* parallax STAMP kit microcontroller requires a USB connection but maybe a Raspberry pi would be sufficient. see also PIC microcontroller
* robotics systems. there are many inexpensive ones that have some programmable logic. Lego robotics mindstorms/nxt is one of the best & there are less expensive models.
* some console games have programming principles built into them. eg Little Big Planet has amazing programming features built into it. there are some handheld versions of programmable games. there are many youtube videos of complex constructions for inspiration.
* smartphones are the new programming world. they have browsers that run javascript, and there are many programming related apps, and one could even surf programming sites with an internet connection (incl wifi).

also suggest as in comments building TM programs eg for addition etc and attempting to follow them by hand.

---
Tags: education
---


# Question
Title: Betweenness Centrality measurement in Undirected Graphs
I'm working with graphs of a very large size (\> 60k vertices), and want to speed up B.C. measurements. It is defined here: http://en.wikipedia.org/wiki/Betweenness\_centrality The algorithm that I am using to compute B.C. is Brandes' algorithm: http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf

For undirected graphs, would running the Betweenness centrality algorithm on each of its connected components (and then combine the results) give the exact same answer as computing on the whole graph at once? I would think so (but don't have a proof) because different connected components are not related.

# Answer
> 4 votes
Betweenness centrality is defined on connected graphs. Suppose a graph $G$ with two connected components, $G\_1$ and $G\_2$, and consider a node $v \in G\_1$, then the betweenness centrality for $v$ is

$$C\_B(u)=\sum\_{s,t \in G}{\frac{\sigma\_{st}(v)}{\sigma\_{st}}}=\sum\_{s,t \in G\_1}{\frac{\sigma\_{st}(v)}{\sigma\_{st}}}+\sum\_{s,t \in G\_2}{\frac{\sigma\_{st}(v)}{\sigma\_{st}}}+2\sum\_{s \in G\_1,t \in G\_2}{\frac{\sigma\_{st}(v)}{\sigma\_{st}}}=$$

$$\sum\_{s,t \in G\_1}{\frac{\sigma\_{st}(v)}{\sigma\_{st}}}+\sum\_{s,t \in G\_2}{\frac{\sigma\_{st}(v)}{\sigma\_{st}}}+2\sum\_{s \in G\_1,t \in G\_2}{\frac{0}{0}}$$

But if you want to treat each connected component as a single graph, you can also calculate the betweenness centrality independently for each component.

---
Tags: graphs
---


# Question
Title: Lower space bound on a turing machine accepting palindromes
Let $$ PAL = \lbrace x \in \lbrace 0, 1, \\# \rbrace^\* | x = rev(x) \rbrace $$ How do I show that a turing machine deciding $PAL$ must use space $\Omega(\log n)$?

I have a feeling that I need to use crossing sequences when crossing the middle of the input tape, but I'm not sure how to relate that to space.

# Answer
> 1 votes
Hint: A Turing machine running in space $S$ runs in time at most $\exp S$.

---
Tags: complexity-theory, turing-machines, space-complexity, lower-bounds
---


# Question
Title: Implementing general vertex folding procedure in an undirected graph
I'm implementing the algorithm presented in *"Improved Parameterized Upper Bounds for Vertex Cover"* paper (PDF). I'm a bit stumped by the `General-Fold` procedure. What it should do is reduce the number of vertices (and) edges in the graph by finding specific structures (almost-crowns) and replacing them with a single vertex. (There is also a separate case, but I'm focusing on the described one now).

It goes like this:

> Let $I$ be an independent set in $G$ (the graph) and let $N(I)$ be the neighbors of I. Suppose that $|N(I)|=|I|+1$ and for every $\emptyset\neq S \subset I$ we have $|N(S)|\geq{S}+1$.
>
> 1) If the graph induced by $N(I)$ is not an independent set, then there exists a minimum vertex cover in $G$ that includes $N(I)$ and excludes $I$). **(This is a 'standard' crown case - I have it implemented already with a separate approach.)**
>
> 2) If the graph induced by $N(I)$ is an independent set, let $G\prime$ be the graph obtained from $G$ by removing $I\cup N()$ and adding a vertex $u\_I$ and then connecting $u\_I$ to every vertex $v \in G\prime$ such that v was a neighbor of a vertex $u \in N(I)$ in $G$.

My problem is **how to find a structure** that would fulfill the suppositions about size as well as having an independent neighborhood? It's all roses when every vertex in $I$ is of the same degree, e.g. ($I$ is yellow, $N(I)$ is green):

which reduces to

or

which reduces to

.

If only that was the case - I'd just check the vertices of a specific degree, descending.

But unfortunately this reduction may apply to a set of vertices of differing degrees. An example:

note the different edges between yellow and green. It also reduces to:

What baffles me is what would the algorithm for that be, since **the paper states** that given a maximum size $k$ of a vertex cover existing in the graph, **it is possible to be done in $O(k^{2}\sqrt{k})$**.

Can anybody offer any help or advice or intuition on this?

EDIT: I think I might be understanding neighborhood incorrectly here - if we suppose that $N(I)$ contains the **intersection** of neighborhoods of every vertex in $I$, this would come down to the first two examples - where every vertex in $I$ is of the same degree...

Any thoughts?

# Answer
> 1 votes
Take a look at the full version of the paper: http://www.sciencedirect.com/science/article/pii/S0304397510003609. What you want is described in Proposition 2.6.

---
Tags: algorithms, graphs, parameterized-complexity
---


title: Weakening and Contraction

text:
# Question
Title: Weakening and Contraction
Wikipedia says that weakening is a structural rule where the hypotheses or conclusion of a sequent may be extended with additional members and that contraction is a rule where two equal (or unifiable) members on the same side of a sequent may be replaced by a single member (or common instance). However, I can't seem to get the terms yet. There are even these symbols that looks like a T turned counterclockwise.

In simple terms, what are weakening and contraction? Can they even be described without the symbol that looks like a T turned counterclockwise?

# Answer
I can't comment about the programming language aspect, but here is the logical aspect. A *sequent* is an expression of the form $$ A\_1,\ldots,A\_n \vdash B\_1,\ldots,B\_m $$ whose meaning is "if $A\_1,\ldots,A\_n$ hold then one of $B\_1,\ldots,B\_m$ holds", that is $$ (A\_1 \land \cdots \land A\_n) \to (B\_1 \lor \cdots \lor B\_m). $$ Sequent calculus is nice since its laws enjoy a certain symmetry between the two sides that reflects the de Morgan symmetry between AND and OR.

Weakening is the law that states that you can a formula to either side of a sequent. That is, if a sequent $\Gamma \vdash \Delta$ is true (where $\Gamma,\Delta$ are sequences of propositions), then for every formula $X$, both sequents $\Gamma,X \vdash \Delta$ and $\Gamma \vdash \Delta,X$ also hold.

Contraction states that if a formula appears twice one of the sides, then an equivalent sequent is obtained by removing the duplicate. That is, if $\Gamma,X,X \vdash \Delta$ then also $\Gamma,X \vdash \Delta$, and similarly for duplicates on the other side.

One more structural rule, permutation, allows us to reorder formulas: if $\Gamma,X,Y,\Delta \vdash E$ then also $\Gamma,Y,X,\Delta \vdash E$, and the same for the other side.
> 3 votes

---
Tags: terminology, programming-languages, type-theory
---


# Question
Title: Looking for an algorithm to solve a specific Vehicle Routing Problem
I am trying to figure out a way to create routes for trucks to complete a list of orders(drops/stops), while *minimizing distance traveled*.

* There is only ever 1 company warehouse in the area.
* The trucks have to deliver *based on capacity*.
* Each truck can hold a maximum (usually 18 pallets).
* Each order will be for a number underneath that maximum.
* There will be a *maximum number of trucks* specified.
* When trucks are finished with their route, they will *return* to the company warehouse.

I already have all of the orders, the pallets they are requesting, and the distance between each point.

I am an absolute *simpleton* when it comes to complex problems like these... I am hoping that someone has a simple (relatively) solution, or an article of some sort that could help me down my path.

# Answer
> -2 votes
A metaheuristic would do. I would opt for a Large Neighbourhood Search (LNS), a Genetic Algorithm (GA), or Tabu Search (TS).

---
Tags: algorithms, optimization, traveling-salesman
---


# Question
Title: Data structure for counting bits set on a table
I have a table that contains only bits. I would like to be able to do the following two queries:

* SET any bit to 0 or 1;
* GET the number of bits that are set to 1 from the beginning of the table up to a specifique index i.

Is there a data structure that is more efficient than a binary indexed tree, i.e. a Fenwick tree? A binary indexed tree performs both operations in $O(\log n)$ time, where $n$ is the number of elements.

For practical info, my tables are really large, containing up to millions of elements.

# Answer
If one of the operations is much more common, you could use an array of bits resp. of counts, so the common operation can be done in $O(1)$ at the cost of the other operation taking $O(n)$.

If you can't make such an assumption, then I don't think there is anything better than the $O(\log n)$ of the BIT.
> 2 votes

---
Tags: algorithms, data-structures, trees
---


# Question
Title: Does register renaming remove all kinds of WAR hazard?
For the following two instruction

```
[Note: MOV Destination, Source ]

i1 : MOV R1, R2
i2 : ADD R2, R3

```

Since i1 is reading from R2 and i2 is writing to R2 there is a WAR data dependency and by register renaming like below we can remove this hazard

```
i1 : MOV R1, R2
i2 : ADD R4, R3

```

What are the other possible situations where such WAR hazard can occur ? and does register renaming solve all kinds of WAR hazard ?

# Answer
> 4 votes
Write-after-read (WAR) hazards are pervasive throughout all of computer systems, although different subfields call it different things. *Renaming* of one kind or another (and called one thing or another) is the most general method I can think of for working around these kinds of problems.

*Register* renaming is the form of renaming used in CPUs that want to expose more instruction-level parallelism. It can be made relatively efficient because the number of programmer-visible register names on most architectures is bounded and small.

From a computer architecture point of view, an additional problem for write-after-read hazards is dealing with load and store operations to main memory. Register renaming won't help with this problem, because the space of visible memory locations is enormous compared to the number of available registers. For this problem a different kind of "renaming" is done where store operations are buffered in a store queue for a period of time. The store queue can be made relatively small because on most CPUs the number of stores that we want to have "in-flight" simultaneously is relatively small. Thus the store-queue can be relatively small and we can afford to have *every* load operation perform an associative search of the store queue.

But the renaming concept is fundamental outside of computer architecture too. An analogous situation occurs in the implementation of any programming language with automatic local variables (which is most programming languages.) You can view the locally declared variables in the source code as analogous to register names and *activation records* (stack frames) as analogous to renamings of the registers. This concept is leveraged in several parallel programming languages, for example in the Id programming language (one of the precursors to Haskell) and the Cilk programming language (an extension to C) the fact that each procedure writes its local variables in a different activation record is used to allow procedure calls to execute in parallel.

In transaction processing systems used in large databases multiversion concurrency control is analogous to renaming. Each transaction sees, and modifies, its own "snapshot" of the entire memory and the snapshots are committed atomically. The snapshots are generally implemented using techniques that are more similar to store queues than to register renaming.

Renaming is also a fundamental technique used in non-blocking synchronization. Suppose you have some container data type (like a map) where you have a unique pointer to the root of the implementation. You can implement lock-free atomic operations by copying the pointer, allocating a new data structure, copying the entire data structure from the old copy to the new, modifying the new version and then trying to compare-and-swap the pointer to the new copy for the pointer to the old copy. Copying an entire data structure would be ridiculously expensive, so in general if you want to do this you would use purely functional data structures.

If you couldn't already tell, this is my favorite topic, and I could go on for hours. So I'll stop here since I've probably written *way* more than you wanted.

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


# Question
Title: What does sublinear space mean for Turing machines?
The problem of deciding whether an input is a palindrome or not has been proved to require $\Omega(\log n)$ space on a Turing machine. However, even storing the input takes space $n$ so doesn't that mean that all Turing machines require space $\Omega(n)$?

Of course, there's no contradiction here, since any function that uses at least linear space also uses at least logarithmic space. But writing $\Omega(\log n)$ does suggest that it's possible for a Turing machine to use less than linear space – after all, why would people spend all that time proving $\Omega(\log n)$ if that was exactly the same thing what seems to be a trivial $\Omega(n)$ bound? So what does it mean for a Turing machine to use less than linear space?

# Answer
When dealing with restricted space, we use the following model. The Turing machine has three tapes: a read-only input tape, a read-write work tape, and a write-only output tape. We only measure space consumption on the work tape. For palindromes, with space $O(\log n)$ on the work tape we can implement FOR loops that go over the input, comparing matching characters on both ends. Each index takes $O(\log n)$ space to store.
> 15 votes

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


# Question
Title: Determining set of states that satisfy a CTL formulae
I'm trying to understand CTL formulae, and until now I've understood everything (or at least I thought I did). I have the following Kripke strucure:

Now given the following CTL formulae `A(g U EG (b v y))` , which states does it satisfy?

I know that the answer is `{s1,s2,s3}` (according to lecture notes), but I don't understand that.

This is what I have tried so far to solve it:

1. I solve `EG(b v y)` first and for this I get `{s1,s3}` because from these states there exists a path where either b or y holds globally.
2. Then I group it together again and solving `A(g U EG(b v y))` which I understand as "Along all paths, g holds until there exist a path where b or y holds" and as I already know the last part of it, I understand it as "Along all paths, g holds until either s1 or s3 holds".

To me s2 is the only obvious answer because g holds in s2 until y holds in s1. I don't understand why s1 or s3, is a part of the answer.

Anyone care to explain? Or at least show the steps you take to derive the answer?

# Answer
The semantics of the "Until" operator allows for the eventuality to be satisfied immediately. That is, $pUq$ holds both in the computation $ppppq$, but also in $q$.

Thus, in your formula, the eventuality is satisfied immediately in states $s\_1,s\_3$, and satisfied within 1 step in $s\_2$. But all of them satisfy it.
> 1 votes

---
Tags: model-checking, software-verification, computation-tree-logic, temporal-logic
---


# Question
Title: How can I simplify the following Product of Sums: ab+ac'+a'b'+a'c+b'c'+bc?
I started with POS: (a+b+c)(a+b'+c)(a'+b+c)(a'+b+c')

and after a long while, I got: ab+ac'+a'b'+a'c+b'c'+bc

and then I'm not sure how to simplify this. I thought maybe I can cancel the ab with a'b', and b'c' with bc and end with ac'+a'c but it doesn't seem to be right if I look at the truth table...

# Answer
**Update** It turns out that your initial simplification was incorrect. Here's a correct one. First, observe that $$ (p+q)(p+q') = pp+pq'+pq+qq'=p +p(q'+q)+0 = p+p1=p $$ so for the first two terms in your POS we have $$ ((a+c)+b)((a+c)+b') = a+c $$ and, similarly, for the last two terms we have $$ ((a'+b)+c)((a'+b)+c') = a'+b $$ so the full product simplifies to $$ (a+c)(a'+b)\quad\text{ or, if you prefer }\quad ab+a'c+bc $$ At this stage you haven't simplified this as much as possible. If you construct truth tables, you'll discover that $ab+a'c+bc=ab+a'c$, in other words the $bc$ term isn't needed here. It isn't obvious how one would discover that unless you've seen Karnaugh maps, for instance.
> 1 votes

# Answer
This is a valid simplification of your problem:

```
(b+c)(a+c)(a'+b)

```

I used Microsoft Z3 - http://rise4fun.com/Z3 with the following code:

```
(declare-const a Bool)
(declare-const b Bool)
(declare-const c Bool)
(assert (and (or a b c) (or a (not b) c)(or (not a) b c)(or (not a) b (not c))))
(apply ctx-solver-simplify)

```

I'm sure you could prove this equality using Natural Deduction or some other rules if you like.

`(a'c)+(ab)` is the shortest equivalent of that expression at the top of the answer.
> 0 votes

---
Tags: logic
---


title: Converting NFA to regular expression

text:
# Question
Title: Converting NFA to regular expression
Here is the regular expression I made for it

This is my first answer, used the naive method aka don't know what am doin' method. $$ \epsilon \cup a^\* \cup (a^\*b) \left((a| b^\*a) | \left( (a|(b^\*a))ba^\*\right) \right) ^\* $$

this is my re-worked answer, with the state removal method.

$$ \left( a^\* \cup (b)(a \cup bb^\*a) \right) ^\* $$

steps taken :

1. Add a new start state and a new final state.
2. Add epsi transitions to the new states.
3. Remove Q2
4. Link between Q1 and Q3 is now $a \cup bb\*a$
5. Remove Q1
6. Add a new link between Q0 and Q3 with $ (b)(a U bb\*a)$ label
7. Remove Q0 There are three paths. a\*, the big regex and the start with epsi $\epsilon \cup a\* \cup (b)(a \cup bb\*a)$
8. Remove Q3
9. We get $\epsilon \cup \left( a^\* \cup (b)(a \cup bb^\*a) \right) ^\*$ =$ \left( a^\* \cup (b)(a \cup bb^\*a) \right) ^\*$

**My questions are:**

* Is my regular expression correct ?
* What happens if it loops ?

To be clear, let's say we have the string aababaaaaabab

I think that string is recognized by the NFA, but I'm not sure it is by my regular expression.

does the $^\*$ at the end cover it correctly ?

ps: As suggested I moved this from math.se

# Answer
For your specific problem, I propose a regular expression in a ad-hoc meth, and the outcome was: (notation comes from Regular Expressions)

> `(a*(b(b+)?ab?)?)*`

I found it with the next methodology: moving from simple to more complex ( states to final states)

* To arrive to $q\_3$, you need to put `a`
* This `a` comes from $q\_1$ or $q\_2$
* If it comes from $q\_1$, use a `b` else it comes from $q\_2$, so use one o more `b`'s: `b+`
* But, $q\_2$ comes from `b` too, so union these two possibilities, `a` comes from `b((b+)?)`
* For that, we have `b(b+)?a` in regular expression to go from $q\_1$ to $q\_3$
* Now, If you want to move from $q\_3$ to $q\_0$, you need a extra `b`, so use `b?`. This is the part of regular expression: b(b+)?ab?
* To start you probably have empty string, or `a`'s or `b` to go from $q\_0$ to $q\_1$
* Above can achieve with `a*` and visit $q1$ or not visit is express like: `a*(b(b+)?ab?)?`
* Finally, you could have a nothing of that, or more than once this strings, so you should use `*`, and take as regular expression: `(a*(b(b+)?ab?)?)*`

## Test Cases

I tested with the next strings and all match with the regex:

1. `aaaaba`
2. `aababaaaaaa`
3. `abbbbbba`
4. `abbbbbbab`
5. `abbbbbbabaaaa`
6. `abbbbbbaba`
7. `bab`
8. `ba`
9. `babaaaa`
10. `aaaaa`
11. `bbba`

In the other hand, you may be interested in consider algorithms to converting DFA to Regular expression, so you can find a dynamic programing algorithm, and the full description of this approach is given in the book of *Models of Computation*, Chapter 4. And other method, Brzozowski algebraic method. All above, because with the powerset constructive you can obtain a DFA from NFA.
> 0 votes

---
Tags: automata, finite-automata, regular-expressions
---


title: Comparing Big O Complexity

text:
# Question
Title: Comparing Big O Complexity
I'm trying to compare two functions, such as f(n)=n^n and g(n)=n^10^10. I'm unsure if f(n) is O(g(n)) or vise-vera where g(n) is O(f(n)). From my understanding, n^n can be worse than n! and although g(n) is being raised to a large constant, it can be bounded by f(n) if multiplied by a certain constant. I am new to this topic, how can you see if a run time function can be bound by another, such as these?

# Answer
If $$\limsup\_{n \rightarrow \infty} \frac{g(n)}{f(n)} \< \infty,$$ then we have that $g(n)$ is $O(f(n))$.

That is actually (almost) the definition of the big-O notation (modulo the $| \cdot |$ function that I left out for readability). You would prove that using your math knowledge. Note that if you can show that $$\lim\_{n \rightarrow \infty} \frac{g(n)}{f(n)} \< \infty,$$ for strictly increasing positive functions $g$ and $f$, this implies the satisfaction of the first equation. Analyzing the latter function should be part of most computer science curricula.
> 1 votes

---
Tags: algorithm-analysis, time-complexity, asymptotics
---


# Question
Title: Finding an exactly weighted st-path in a digraph
I have a weighted digraph graph $G = (V,E)$ where the weights are positive and negative integers. The graph $G$ is not necessarily acyclic.

The question is: given 2 nodes $v\_1$ and $v\_2$, is there a path from $v\_1$ to $v\_2$ with a weight $w$.

I would like to know if there are any known complexity results for this problem, or even anything related to this **but** with a specific weight, and not just shortest path, longest path etc.

# Answer
This problem is NP-complete.

A reduction from subset sum:

Given numbers $\\{x\_1,\ldots,x\_n\\}$ and a target number $T$, construct the complete transitive acyclic graph $G=(\\{x\_1,\ldots,x\_n\\}\cup \\{v\_1,v\_2\\}, E)$,

Where $E=\\{(v\_1,x\_i) \mid i\in \[n\]\\}\cup \\{(x\_i,v\_2) \mid i\in \[n\]\\}\cup \\{(x\_i,x\_j) \mid 1\leq i\<j\leq n\\}$, and $w(x\_i,v\_2)=0$, $w(v\_1,x\_j)=w(x\_i,x\_j)=x\_j$.

Now simply ask if there exists a $v\_1\leadsto v\_2$ path of weight $T$.
> 2 votes

# Answer
This problem is NP-complete.

The "$\in$ NP"-part is trivial.

For the NP-hard part we reduce directed hamiltonian path:

> Given a directed graph $G=(V,E)$ and two vertices $v\_1,v\_2\in V$, is there a path from $v\_1$ to $v\_2$, that visits each vertex exactly once?

For the reduction we keep $G$, $v\_1$, and $v\_2$ and number the nodes from $1$ to $n$, so that $v\_2$ gets the number $n$. Then we assign each edge from node $i$ to node $j$ the weight $2^n+2^i$ and ask for a path of weight $n\cdot 2^n-1$.

It is easy to compute, that a hamiltonian path will have the correct weight.

For the other direction note that any path that takes $n$ steps or more would have a weight above $n\cdot 2^n$ and thus be invalid. A path that only takes $n-2$ or fewer steps on the other hand would have a weight below $(n-1)\cdot 2^n$, which is also invalid. So any valid path will have a length of $n-1$.

Furthermore the required weight has the bit for $2^i$ set to $1$ for each $0\<i\<n$. In order to achieve this without visiting node $i$, we would need to visit node $i-1$ (or a node with a smaller number) multiple times. But we only have $n-1$ steps to set $n-1$ bits. So only hamiltonian paths can achieve the correct weight.

The reduction works in polynomial time, since the size of the binary encoding of the weights and target is linear in the number of nodes.
> 4 votes

---
Tags: complexity-theory, graphs, decision-problem
---


# Question
Title: Is finding if a graph has k isolated nodes a NP-Complete problem?
I was wondering if finding if a graph has k or more isolated nodes is a NP-Complete problem. I found the following problem:

> Prove that the following problem is NP-Complete. Given a set of T transactions: $T = \\{t\_1,t\_2,\dots,t\_m\\}$ where each transaction $t\_i$ is a pair of banks $(b\_{i1},b\_{i2})$. Find if, given an integer value k, there is a group of k banks that doesn't perform any of the given T transactions.

I was thinking to proceed this way:

1. Input complete graph with all the Banks: $G=(B,E)$
2. Subtract to E the T set, I obtain a new graph, $G'=(B,E\setminus T)$
3. Find if there's an existing k-clique in $G'$

Is there any more effective way to solve this problem?

# Answer
No, determining whether a graph has $k$ isolated vertices is not1 **NP**-complete. Just count the number of isolated vertices and compare against $k$. This can be done deterministically in linear time (linear in the size of the graph's description; possibly quadratic in the number of vertices).

1 Unless **P**=**NP** and, even then, it might not be **NP**-complete.
> 2 votes

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


# Question
Title: Count points enclosed by several planes in 3D space
I have for example 10 planes with their equation: Ax + By + Cz = D and a list of 3D points. Those plane can make regions, some of them closed, and others not, the task is to count the number of points in each region.

I just need some ideas about how to solve, or if there is an algorithm for that.

# Answer
> 2 votes
Each of the plane can be considered as a constraint which might hold with =, \<, or \>. A point lies either on the plane or on one of the sides. This can be decoded by a `+`, `-` and `0`. Say the string `+++++-----` decodes the cell for which the first 5 constraints hold with \>, and the last 5 with \<.

You can now go through all the possibilities. Start with the first plane and filter the points with respect to this plane. You will get three sets. Then use recursion to subdivide the sets further. If the recursion stops (that is you processed the 10th plane), you count the remaining set.

Regarding the running time. If you have $n$ points and $m$ planes then $$ T(n,m)= T(n\_1,m-1)+T(n\_2,m-1)+T(n\_3,m-1) + O(n)$$ for $n\_1+n\_2+n\_3=n$. This solves to $O(nm)$. You can use induction on $m$ to prove this.

# Answer
> 2 votes
A plane divides the 3D space in two regions. A good method to discern is to apply the plane equation to the point and see if it yields negative or positive result:

$$Ax + By + Cz + D = 0$$

is the equation of a plane in 3D. So if you put the point coordinates you'll get a positive, zero or negative number. (If zero, the point belongs to the plane and so, it's neither in either side of the plane.)

The question asks to count the points that belong to each of the delimited regions for each plane. Well, you have n planes each dividing the space in two halves (so you have $2^n$ regions at most, except in case you have paralell planes, but this procedure is applicable also in that case ---you'll get regions not accounted for as no point can lie in them), just consider each point and apply it to each plane. Then construct a number X, making bit $i$ (for plane $i$) of X a 1 in case applying plane to it gives a positive number and 0 in case applying it gives a negative one (in case it returns 0 you have to decide what side to count it ---what value you select for bit $i$--- for (if any) as this is a point that belongs to the plane) then with that number as a key for region X, increment counter of region X selected, so in one pass over all points you'll get all counters actualized with how many points belong to each region. Each key X, so constructed, identifies each of the possible regions you have divided the space into, so you must cope with $2^n$ regions (and counters) for $n$ planes.

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


# Question
Title: Understanding when to count key comparisons
I understand that for something like Linear search, this would be the key comparison:

```
 if(itemToFind == a[i])
    return i;

```

If I put this method into another method, say a Sorting method, do I still count the linear key comparison plus the sorting key comparison? Or do I only care about the sorting key comparison?

Example:

```
 public class SortAndSearch{

 void QuickSortAndSearch(A, p, r){
      if(p<r)
         q = Partition(A,p,r)

      if(itemToFind == a[i])
    return i;
 }

```

# Answer
> 1 votes
I'll answer some other question first: **Why do we count key comparisons?**

When analysing the runtime of an algorithm it can be tedious to count all the operations (even more so, if we notice they don't all take the same time). So it is convenient to identify those operations that dominate the runtime and only analyse those.

In the case of searching the dominant operation are key comparisons, in the case of sorting, they are key comparisons and swaps. Furthermore, most sorting algorithms will only swap elements that they have compared just prior. Thus the number of comparisons gives an upper bound for the number of swaps as well. So we can get away with counting the number of comparisons in order to get an idea of how the (worst-case) runtime of an algorithm behaves.

Now to your actual question:

If key comparisons are the dominant operation, e.g. in an algorithm that combines sorting and searching, then it is useful to count all key comparisons, if we want to get an idea of the runtime.

If, on the other hand the key comparisons are dominated by some other operation, then it might make more sense to count those other operations and not count any key comparisons.

Or the key comparisons are one of several operations, neither of which dominates the others, then we count all of those. Or in one part of the program key comparisons are dominant, while in another part they are not. Or ...

---
Tags: algorithm-analysis, time-complexity
---


title: BNF and Simultaneous Parsing

text:
# Question
Title: BNF and Simultaneous Parsing
Let's say we have the following grammar

```
expr1 ::= ... // Actual definition doesn't matter
expr2 ::= ... //
expr3 ;:= ... //
foo ::=  expr1 | expr2 | expr3

```

When it comes to parsing **foo** we note that **foo** could be parsed in parallel.

```
p1 = task parse( expr1 )
p2 = task parse( expr2 )
p3 = task parse( expr3 )

```

**Question**

Would continuing on the first to complete be better.

```
result = task.WaitAny( p1, p2, p3 ) // wait for any (parsing) task to complete

```

or would it be better to wait for all the (parsing) tasks to complete?

```
task.WaitAll( p1, p2, p3 ) // wait for all (parsing) task to complete

```

What are the potential issues with simultaneous parsing?
or
Does the ordering of clauses matter?

# Answer
If the grammar is amenable to limited-lookahead bottom-up parsing, then the parallelism is more or less implicit in the parsing algorithm, and there is little to be gained from parallel computing, at least in the sense proposed in the post. A standard LALR(k) parser is deterministic; it only does a single table-lookup for each action, based on the current state, the lookahead token(s) and -- in the case of reductions -- a single state value popped from a known location on the parse stack.

That's not to say that there is no possible benefit from the availability of multiple CPUs, but I suspect that benefit would come from segmenting the input using some kind of simple lexical analysis (text inside balanced braces, for example) and constructing individual parse trees for each segment.

If the grammar itself is highly ambiguous, as is the case for natural-language parsing, then different algorithms will be employed. CYK parsing, for example, used as the basis for many probabilistic parsers, can benefit significantly from parallel processing, and it is easy to find recent (and not-so-recent) papers on the subject on the internet. I found a dozen in a few seconds, and I won't bother pasting all of them particularly since I didn't read them, but I think that this paper by Mark Johnson has some pretty impressive results.

The answer dodges around the actual question, because I think the algorithmic analysis required to efficiently parallelise chart-parsing is more sophisticated than simply exploring alternative productions in parallel. But I hope it has some utility.
> 5 votes

# Answer
I think that rici's answer is a good summary of the situation. As he remarks, there is probably not too much to expect from from parallel computing in the case of grammars that lend themselves reasonnably well to deterministic parsing.

I am not sure whether the answer is the same when deterministic parsing requires heavy changes in the grammar structure, even assuming these changes are reversible, so that whatever parse tree is produced with the transformed grammar can be transformed back into a parse tree for the original grammar.

The Johnson paper, which I skimmed, seems to contain interesting considerations and experimental results. However, you should keep in mind that parsing is not a single problem. It does have many variants, depending on whether your language is deterministic, or just unambiguous, or possibly ambiguous but you want only some parses based on diverse criteria, or whether you want all parses, possibly to select from them on the basis of further processing. Non deterministic or ambiguous parsing is usually based on dynamc programming techniques, the best known of which are CYK and Earley's algorithm. But there are other views of it (see below).

Apparently, the Johnson's paper focusses on one of these categories: very ambiguous probabilistic grammars with Viterbi selection of the best parse, integrated in the algorithm.

If you were interested in getting the whole parse forest, representing all possible parses, there is a possibility that the results might be different.

On the other hand, both problems rely on a vision of the parsing process as computing an answer in a semiring algebra, so that the difference is not so much in the logic of the computation as it is in the data structures computed with. But parse forest are heavier structures to manipulate than are single trees with probabilities. I have no idea how much this would impact a complexity analysis.

Another point is that the semiring structure is an abstraction, but the same parse forest (seen semantically as a set of parse trees) may have many syntactic representations, some more condensed, or better organized, than others. Parallelization on multiple processors is very likely to have an impact on the syntactic representation of the sharing structures of the parse forest, which could impact further processing, unless it is also integrated adequately in the parallelization scheme.

It might be worth analyzing the problem abstractedly as a semiring evaluation procedure. There is some literature on that, and one place to start from might be Joshua Goodman's "Parsing inside out", though he does not address parallelization (afaik).

Another way to look at your question is parsing as intersection, i.e. to see parsing as the construction of the CF grammar $L\_A$ for the intersection of the languages of another CF grammar $L$ and a NFA $A$. The main difference is that parsing corresponds to the case where the graph of the DFA is mostly acyclic (some cycles may be considered for special purposes such as handling of errors or ill-formedness). Possibly that view of the problem could lead to some insight.

Coming back to your question of whether alternative rules for a terminal could lead to parallelization. I would try tp look at it from the point of view of intersection with NFA.
> 1 votes

---
Tags: parallel-computing, parsers, parsing
---


title: Mutual information intuition

text:
# Question
Title: Mutual information intuition
I was creating an example for a casual talk on mutual information. I considered a system of two coins, which with probability 1/2 are copies of each other, and with probability 1/2 are independent.

Then $P(A=B)=1/2+1/2\times 1/2=3/4$, so $P(HH)=P(TT)=3/8$ and $P(HT)=P(TH)=1/8$.

Total information is then $E(-\log\_2 p) = 1.81$.

Therefore mutual information is $H(X)+H(Y)-I(X;Y)=1+1-1.81=0.19$ bits.

Is this correct? Because intuitively in this case one might expect, as 50% of the times the coins are equal, the mutual information is $0.5$ bits.

Is there any simple intuition why it is less than $0.5$ bits?

# Answer
Mutual information tells you how much you learn about $X$ from knowing the value of $Y$ (on average over the choice of $Y$). In other words, mutual information measures how many fewer bits you need to encode $X$ if you already know $Y$, than if you didn't. In your example, learning $Y$ enables you to guess $X$ correctly with probability 0.75, but as $H\_2(0.75)\>0.5$ ($H\_2$ being the binary entropy function), you still need more than half a bit to encode the correct value of X even if you know Y. So your "savings" in encoding length are less than 0.5.

Here is a more illustrative example, I think. You have three random bits, $X$, $Y$, $Z$. $X$ and $Y$ are independent and unbiased, while $Z$ is the exclusive or of $X$ and $Y$. Then $H(X,Y) = 2$, while $H(X,Y|Z=z) = 1$ for any $z \in \\{0,1\\}$, because knowing $z$ and the value of $X$ determines $Y$. Then $I(X,Y;Z) = H(X,Y) - H(X,Y|Z) = 1$. In words, if you know $Z$ you only really need to encode $X$ rather than both $X$ and $Y$.
> 7 votes

---
Tags: probability-theory, information-theory, entropy
---


# Question
Title: Is an algorithm in pseudocode a reasonable way to establish complexity?
We define the language

$$ L = \\{a^nb^n : n\geq0 \\} $$

and we want to prove the following

$$ L = \mathrm{DSPACE}(\log n)\\,. $$

So we have to prove that by using $\log n$ space on the work tape of a Turing machine we can decide this language. In this case, do we have to describe the delta function in detail, or can we just use the Church Turing thesis and show an algorithm that uses $\log n$ space to decide this language, and thus claim that $L$ is indeed in $\mathrm{DSPACE}(\log n)$?

For example the pseudocode for the above language would be the following:

```
    number_of_as = 0
    number_of_bs = 0
    tmp = read()
    while(tmp == a)
          number_of_as++
          tmp = read()
    if(tmp == b) number_of_bs = 1
    tmp = read()
    while(tmp == b)
          number_of_bs++
          tmp = read()
    if(number_of_as == number_of_bs) "accept"
    else "reject"

```

we only use two counter and the `tmp` variable, for each variable we need $\log n$ space, so in total $3\log n$, so the problem is in $\mathrm{DSPACE}(\log n)$.

# Answer
To state the obvious, you need to prove that the language is decided by some Turing machine that uses a logarithmic amount of space on its work tape.

Anything beyond that is a question of how rigorous the proof should be. A proof should be rigorous enough to convince an appropriately skeptical reader. How much skepticism is appropriate in a given situation? Well, that's a largely social construct. If we were chatting during a coffee break at a complexity theory conference, I'd probably be convinced by "Oh, just use a couple of binary counters to remember how many $a$s and $b$s you've seen. The input has length $n$ so the counters only need $\log n$ bits each." If I was marking your undergrad complexity theory exam, I'd expect rather more detail. For example, our conference chat didn't include the fact that the machine should reject if it finds an $a$ after the first $b$ and your pseudocode also misses this, so it accepts the string $aba\notin L$.

Expecting a full definition of the Turing machine is probably unreasonable. First, it would take a long time to produce. Second, and more importantly, it would be sufficiently complicated that it would be hard to verify that the Turing machine really does what you claim it does. A proof that is too complicated for anyone to understand isn't really a lot of use. That being the case, you're pretty much going to have to use pseudocode. If I wanted to test that you could produce a formal description of a Turing machine, I'd use a simpler language, such as the strings with an even number of $a$s in them.

Is pseudocode on its own enough? Not quite. For example, you can't just invoke Church–Turing to convert your pseudocode into a Turing machine. Why not? Because Church–Turing preserves computability but not complexity. So, what does an answer need? I would say the following.

1. Pseudocode for an algorithm.
2. If it's not obvious, a proof (with an appropriate level of rigour) that the pseudocode actually solves the required problem.
3. If it's not obvious, a proof (with an appropriate level of rigour) that the pseudocode can be converted into a Turing machine with the appropriate resource bounds.

Even if you think the two proofs *are* obvious, it's a good idea to write a sentence or two about them. Trying to explain as briefly as possibly why something is correct can often find bugs such as the $aba$ problem.
> 4 votes

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


# Question
Title: NFA state complexity for the complement of EPAL restricted to a fixed length
I've been having trouble proving the next statement:

> Let $L\_n=\\{ww, |w|=n\\}$ (the set of equal-length palindromes (EPAL) restricted to length $2n$). Prove that $L^c\_n$ can be accepted by an NFA with at most $O(n^2)$ states.

What I've been trying to do is that the complement of $L\_n$ is

$\qquad\displaystyle L^c\_n = \\{w , |w| \not = 2n\\} \cup \\{ww', w \not = w'\\}$.

I want a hint on what to think to prove this thanks!

# Answer
Hint: further break up the difficult case $\\{ww' : |w|=|w'|=n,w\neq w'\\}$ as a sum $$\bigcup\_{i=1}^n \\{ \Sigma^{i-1} \alpha \Sigma^{n-i} \Sigma^{i-1} \alpha' \Sigma^{n-i} : \alpha \neq \alpha' \in \Sigma \\}. $$ In total there are $n+1$ cases (including $\\{w : |w| \neq 2n\\}$), so if you can implement each one in $O(n)$ states, you're done.
> 3 votes

---
Tags: formal-languages, regular-languages, automata, nondeterminism, descriptive-complexity
---


# Question
Title: Is there a difference between the Bulk Synchronous Parallel Computing model and the Turing Machine
The Turing model of computing is widely accepted, as a Tape, Head, State register, and a finite state Table to manage transitions. The Bulk Synchronous Parallel Machine model has for its part similarity to the PRAM model, but with additional features in state management, by communication, and synchronization. So, in a sense it implies barrier synchronization, communication, and concurrent communication implicit in its workings, with processors having an order imposed on them. Does this conflict with the Turing machine model(?). Can one simulate one model by the other? Are they equivalent, or are there differences between these models?

# Answer
> 2 votes
I don't know the particulars of the bulk synchronous parallel machine, but it is highly likely that both have the same computational power, that is, both machines compute exactly the class of recursive languages. The difference between the models lies in their corresponding complexity measures: a language that has a certain (time or space) complexity in one model could have a different complexity in the other model.

---
Tags: turing-machines, parallel-computing, synchronization
---


# Question
Title: Polynomial time optimisation algorithm for a poly-time computable function with bounded number of maxima?
Suppose we have a polynomial time algorithm for computing a function (we think of as existing on rational numbers between $0$ and $1$ of limited binary length n). We know that this function is made up of $m$ strictly monotone functions or equivalently that it has up to $m-1$ maxima/minima. Can we find these maxima in time that is polynomial in $m$ and $n$?

# Answer
Hint: Consider a function that is increasing, except in the small interval $\[a,a+\varepsilon\]$, where it decreases slowly. Assume $\varepsilon\>0$ is very small and the value $a$ is not known a priori. Can you find the maxima in polynomial time?
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Maximum value a variable can hold without documentation
Suppose we work with some particular programming language (like C++) on some particular computer. Furthermore, we want to know which values are minimum and maximum for some particular numeric data type of this language. We can't use any specific tools of our language (like numeric\_limits), and have no access to language or system documentation. Specifically, we don't know the lengths of our words. Is there an effective and rather precise way to find out the min/max we want to know?

We can certainly write some loop starting with zero and adding one at each step and wait for an overflow. But it is certainly not an effective way. We can write some loop and check some condition like $\log(\exp(n)) \stackrel{?}{=} n$, but I'm not sure whether this will answer our question.

# Answer
> 5 votes
The first step should be

```
count = 0
while (x*2 > x)
  x = x*2
  count++

```

to find the largest power of 2 that can fit into the variable. Note that doing `+1` instead of `*2` is not only much slower but also fails for floating point numbers (the gaps between large consecutive floating point numbers are bigger than 1). The above procedure should work for both numbers that roll over and numbers that reach infinity.

Once you have a rough estimate, you may perform a binary search in the range from `estimate`, to `2*estimate` to find an exact bound.

---
Tags: algorithm-analysis, formal-methods
---


# Question
Title: Is the "data path cycle" the same thing of the "fetch-decode-execute cycle"?
I am reading the book `Structured Computer Organization` (5th edition) by *Tanenbaum* and at a certain point, in the second chapter, he talks about `data path cycle` and `fetch-decode-execute cycle`, and I am not understanding if they are really the same thing.

The data path cycle should be the number of small and minimal steps that a CPU goes through each cycle. On the other hand, the fetch-decode-execute cycle is the number of small steps that could be generalised like this:

1. Fetch the instruction from the memory and put it into a register
2. Change programming counter to point to the next instruction
3. Determine the type of the instruction fetched
4. If the instruction uses a word, determine where it is
5. Fetch the word, if needed, into a CPU register
6. Execute instruction
7. Go to step 1.

The fetch-decode-execute cycle is `common to all computers`, so each data path cycle should be a fetch-decode-execute cycle, right?

# Answer
*Data path cycle* is not widely used terminology. I believe Tanenbaum made it up. I don't have the 5th edition, but if I look up Tanenbaum's slides on Google (for example: http://www.verlab.dcc.ufmg.br/\_media/cursos/arquitetura/2011-1/transparencias/tanembaum\_4.pdf) it appears that he is using *data path cycle* to refer to a single *clock* cycle. As in "the amount of time for all the signals to propagate all the way through the data path." Think of it as the amount of time required to perform one *micro*-instruction.

But Tanenbaum uses a multi-cycle-per-instruction microcoded organization, so the *fetch-decode-execute* cycle (for instructions rather than microinstructions) usually involves multiple clock cycles.
> 3 votes

---
Tags: computer-architecture
---


# Question
Title: Spatial Locality in Cache - Which addresses are loaded?
I don't quite understand the concept of spatial locality in cacheing. I understand that on a cache miss, not only the specific address we want is loaded into the cache, but also "nearby addresses" are loaded too.

However, I can't understand WHICH addresses are loaded. I have an assignment with the following question:

```
The cache consists of 16 words (4 bytes for each word), and is arranged in blocks of 2 words each.
The following addresses are in BYTES in decimal base. The cache is initially empty.
12,8,24,28,36,44,48,52,60,64,68,76,136,140,144,148,152,220,224,228,220,224,228
Determine what are the addresses which are a MISS (determine whether it's a valid or a tag miss).

```

What is hard for me is to understand which addresses are loaded, when, for example, the address 12 is reached. Is 13 loaded into the cache? 14? 15? or maybe 11? How do I know that?

I think that if understand this fundamental question, I could answer this question with ease.

# Answer
> 3 votes
When inserting an entry in the cache, an entire block of addresses is copied. In your case 2 words (8 bytes) are inserted.

So when address 12 is reached, the block of 8 bytes having address 12 is inserted into cache.

Likewise in case of subsequent misses a maximum of 8 such "blocks" can be inserted into cache, after which eviction process shall start. Further sequence of cache hits/misses shall depend on the eviction policy.

# Answer
> 1 votes
Cache works at the granularity called "cache lines" which are loaded to the cache when ever any byte in the line is accessed. For example if the line size is 8 bytes, and you read byte at address 12, then all bytes from 8 to 15 are loaded to the cache.

There is more to the story though called "associativity" that influences the data kept in the cache. In your assignment due to the order the addresses are accessed the associativity doesn't change the answer, but it's good to be aware of this trait to better understand cache behavior. For example if there was byte at address 12 addressed at the end of the sequence then associativity would influence the answer to your assignment.

There is "fully associative" cache where any cache line address in the memory can reside in any location in the cache. This is the most efficient policy regarding the use of cache memory but also the most costly regarding performance. There is also the opposite "direct mapped" caching policy where memory addresses are directly mapped to addresses in the cache (e.g. for cache size of 64 bytes first "address mod 64" is calculated and that's used to determine the location in the cache) and thus each memory address has effectively only one valid location in the cache. This is the most wasteful policy regarding cache space but most efficient performance-wise. Then there is "N-way associative" caching policy that's the compromise between the two and the mostly used caching policy in practice, where each memory address can reside in N locations in the cache. In N-way associative cache the cache is split to N direct mapped caches and search for the line is performed between the N locations in these caches upon memory access.

The associativity plays a role when new data is loaded to the cache and thus some other data must be evicted from the cache. Normally caches use "least recently used" (LRU) eviction policy, i.e. for the valid cache line locations (determined by the associativity) in the cache, the line that was accessed the longest time ago is evicted.

---
Tags: cpu-cache, memory-hardware
---


# Question
Title: How to prove strict space lower bounds using crossing sequences in Turing machines?
I understand the notion of crossing sequences when talking about time, however how are they used to actually prove strict lower bounds for some decision/search problems?

For example, suppose that you have an array of size N and you want to find the maximum number in it.

Speaking informally, we need at least a pointer to run through the input and some other variable to update whenever we find a number in the input tape that is bigger than the temporary number in our work tape, thus leading us to use Ω(logn) space.

However, how can you prove that you can't do it in O(1) space? Many articles online are using crossing sequences for proving space lower bounds, but they don't show how to do it, they just say something along the lines of "using crossing sequences it's trivial to show that the space lower bound is ..."

which isn't very helpful for beginners like me. Thanks!

# Answer
> 1 votes
A deterministic algorithm running in space $S$ runs in time $\exp S$. If you don't go over the entire array then you don't know the maximum number (formally speaking, consider two arrays differing in the last element, in only one of which it is the maximum). It takes time $n$ to go over the entire array. So $S = \Omega(\log n)$.

---
Tags: turing-machines, proof-techniques, space-complexity
---


# Question
Title: Etymology of time and space "complexity"
The word choice of "complexity" in analysis of algorithms to describe temporal and spatial resource requirements has always struct me as an odd one. These are certainly useful and meaningful concepts. This question is concerned with the language used to describe them.

Colloquially, one would probably not say that insertion sort is more "complex" than radix sort.

Is the origin and rationale of this word choice known? If so, what is it?

# Answer
> 4 votes
*Complexity* refers to the complexity of the computation rather than the complexity of the algorithm. For example, Ritchie's Classes of predictably computable functions from 1963 "\[studies\] a sequence of classes of computable functions for which a prediction of the complexity of the calculation may be made in a comparatively simple fashion."

Hartmanis and Stearns, in their seminal 1965 paper On the computational complexity of algorithms, also use complexity in a similar sense: "One finds, however, that some computable sequences are very easy to compute whereas other computable sequences seem to have an inherent complexity that makes them difficult to compute." This paper is the source of the terminology, though they cite earlier papers (like Ritchie's from 1963) which had already used complexity in this sense.

---
Tags: terminology, algorithm-analysis, history
---


# Question
Title: How to avoid cascading resizes when resizing hash tables?
With conventional collision resolution methods like separate chaining and linear/quadratic probing, the probe sequence for a key can be arbitrarily long - it is simply kept short with high probability by keeping the load factor of the table low. Collisions during rehashing thus aren't a problem as they don't affect the load factor.

However, with cuckoo hashing (and other methods offering worst-case O(1) lookup time?), a resize *must* happen when the probe sequence for a key gets too long. But when the keys get shuffled around during the rehash, it may be that they create a too-long probe sequence for one key, necessitating another resize - possibly several, if this happens multiple times in a row. The probability is small, especially with a good hash function, but I've seen it happen.

Is there a way - short of explicitly generating a perfect hash function during the rehash - to ensure that resizes can't cascade in this manner? Possibly specific to a given collision resolution scheme? The literature I've encountered thus far seems to gloss over the matter entirely. Bear in mind that I'm also interested in *shrinking* hash tables, not just growing them.

# Answer
You ask how to avoid cascading rehashes but you already gave the answer in your post. You keep the probability that *bad events* occur small.

Since you mention cuckoo hashing. The probability that you get a long probing sequence is $O(1/n^2)$. So if you rehash, you are inserting $n$ elements from scratch. The probability that the rehash is not successful is then $O(1/n)$, so with very high probability you are successful. In expectation you need only a constant number of tries. If you observe that you have problems with rehashing, then you should increase your table size and modify your load factor. Alternatively you can select a better family of hash functions.
> 1 votes

# Answer
I believe I have one solution, inspired by linear hashing:

If the hash function(s) is held constant (that is, not changed when resizing) and the table is always grown by doubling the slots, then after the table is grown, it holds that

$H \mod 2L = \begin{cases} H \mod L + L & \text{or} \\ H \mod L \end{cases}$

where $H$ is the hash of a key and $L$ is the old number of slots. This means that a key either stays where it is or moves to a unique slot in the newly allocated area, which is guaranteed to be empty.

To apply this to (d-ary) cuckoo hashing, simply resize each of the subtables individually and don't move keys between subtables.

To shrink the table, you need to confirm that one of $\lbrace H \mod \frac{L}{2} + \frac{L}{2}, ~ H \mod \frac{L}{2} \rbrace$ is vacant for every key in the table, and if so, move them all to their $H \mod \frac{L}{2}$ slots. Of course, this is $O(n)$... I'm not sure if there's a better way to do this than running the check for every deletion once the load factor drops below half.
> -1 votes

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


# Question
Title: Determining on whether topology is a tree or a hypercube
Assume that the nodes know that the topology G is either a hypercube or a tree. Assuming a unique initiator, design an algorithm to discover the topology. In other words, you would like a node to reach terminal state TREE if G is a tree, terminal state HYPERCUBE if instead it is a hypercube. Let n be the number of nodes and m the number of edges, you would like to exchange O(m) messages in the worst case.

I will use DFS until I either:

* reach a leaf or
* a node that has been visited before.

In the first case it is a tree and in the second one it is a hypercube. How does this sound?

In the below code, I assume every the graph is tree. But If I see cycle, I change the STATE to HYPERCube. This happens when a node gets the token twice.

Sample Pseudocode

```
Initiator
    Spontaneously
    begin
        Unvisited:= N(x);
        initiator:= true;
        VISIT;
    end

IDLE
    Receving(T)
    begin
        entry = sender;
        unvisited:= N(x) - {sender};
        VISIT;
        STATE = "TREE";
    end

VISITED
    Receiving(T)
    begin
        STATE = "HYPERCUBE"
    end

    Receiving(R)
    begin
        VISIT;
    end

Procedure VISIT
begin
    if Unvisited =! 0 then
        next = Unvisited
        send(T) to next;
        become VISITED
    else
        if not (initiator) then send(Return) to entry endif
        become DONE;
    endif
end

```

# Answer
> 1 votes
As you have noticed, a simple solution is to generate a token at the initiator and then forward the token through the network using a DFS strategy.

If this token encounters a node that is a leaf, the node will record this information in the token before it is sent back. So when the token has completed the DFS, it will have returned to the initiator who then inspects the token to check if it has encountered any leaf.

The O(m) message complexity follows from the message complexity of DFS, and to show this it's sufficient to prove that the token is sent a constant number of times over each edge.

---
Tags: trees, distributed-systems, topology
---


# Question
Title: Prove any binary tree with $n$ nodes has at least $1+\log_2 n$ levels
Prove that any binary tree with $n$ nodes has at least $1+\log\_2 n$ levels. I tried setting $n=8$ and plugging in $8\geq\log\_2 8 = 8\geq 3$. But I'm not sure how I can prove this by induction.

# Answer
> 1 votes
Hint: A binary tree with $1+h$ levels contains at most $1+2+2^2+\cdots+2^h = 2^{h+1}-1$ vertices.

---
Tags: graphs, binary-trees
---