# Question
Title: Why is the most probable assignment for all variables in MRFs called MAP assignment?
I am new to graphical model, especially Markov Random Fields. I have a question about MAP assignment. Let say we have the graph structure and all the potential functions. MAP assignment in MRFs is defined as the most probable assignment for all variables (no given evidence in this case). My question is why it is called MAP (why not MLE or anything else). What is the connection between them? I know MAP and MLE share a lot in common except for one thing that MAP uses the prior distribution of the parameters. But I cannot figure out the connection between the most probable assignment in MRF and MAP.

# Answer
> 1 votes
MLE is a point estimate $\hat{\theta}\_{\text{MLE}}$ that resides at a mode of the likelihood density. That is, $$L(\theta; X) = \Pr(X | \theta)\\ \hat{\theta}\_{\text{MLE}} = \arg \max\_{\theta} \Pr(X | \theta)$$

MAP stands for maximum a-posteriori. It is a point estimate $\hat{\theta}\_{\text{MAP}}$ that resides at a mode of the posterior distribution (the distribution over the parameters themselves conditioned on our observed data). We can perform MAP estimation by incorporating a prior distribution for our parameters.

$$ \Pr(\theta | X) = \frac{\Pr(X | \theta) \Pr(\theta)}{\Pr(X)} \\ \Pr(\theta | X) \propto \Pr(X | \theta) \Pr(\theta) \\ \hat{\theta}\_{\text{MAP}} = \arg \max\_{\theta} \Pr(X |\theta)\Pr(\theta)$$

This is a simple application of Bayes' Theorem. The reason we use "proportional to" is that we don't care about the marginal likelihood constant. Since it is only a constant our point estimate for this "psuedo-MAP" still corresponds to a point-estimate for the true MAP. By definition $\hat{\theta}\_{\text{MAP}}$ is the (at least locally) most-probable estimate under the posterior distribution.

The key take-away is that the Maximum Likelihood estimate is the point estimate that maximizes the probability of observing your data. The MAP estimate is the point estimate that is the (at least locally) most probable under your posterior distribution of parameters. In the end deciding whether to use the MLE or MAP estimate is up to you and your model. It really depends on what you are more interested in.

To stress the difference one last time, look at the difference between the two definitions for the distributions being maximized over. In ML estimation we are maximizing over the distribution of observing our data; in MAP estimation we are maximizing over the distribution of parameters themselves. Hence why we can say MAP estimates are the most-probable estimate whereas we cannot for the ML estimate.

---
Tags: machine-learning, probability-theory
---


title: Why is a superscalar processor SIMD?

text:
# Question
Title: Why is a superscalar processor SIMD?
1. From http://en.wikipedia.org/wiki/Superscalar

> In Flynn's taxonomy, a single-core superscalar processor is classified as an SIMD processor (Single Instructions, Multiple Data),

Flynn's taxonomy is based on number of instruction streams and number of data streams.

A superscalar processor can run more than one instructions at a time, so why isn't it MIMD?

If there is a valid reason for a superscalar processor to be SI, then why isn't there a similar reason which makes it single-data (i.e. SISD)?
2. Instruction pipeline also runs more than one instruction at one time. Is it SISD or SIMD?
3. Does "SI $\equiv$ only one CPU core"? Or only one implies the other?

Does "MI $\equiv$ more than one CPU cores"? Or only one implies the other?

Thanks.

# Answer
> 9 votes
First, Wikipedia is wrong in classifying superscalar processors as SIMD (except as many modern superscalars also support short vector instructions). A superscalar has one instruction **stream**, i.e., there is conceptually only one current instruction address from which instructions are fetched. However, it also has only one data stream, i.e., it generally does not apply the same instruction to multiple data as a vector processor would. (from "Some Computer Organizations and Their Effectiveness" (Michael J. Flynn, 1972): "The single-instruction stream-multiple-data stream (SIMD), which includes most array processes, including Solomon \[2\] (Illiac IV).")

Pipelining does not increase the number of instruction *streams* being processed in parallel; the single stream simply flows through a longer channel as it were.

A single processing core *can* have multiple instruction streams by using multithreading. (Multithreading cores often present this as virtual cores, i.e., to software each thread appears to have a full core, as a convenience for operating systems, allowing any multiprocessor-capable OS to trivially support multithreading. However, this is not a necessary feature; the MIPS MultiThreading Application Specific Extension, e.g., differentiates between a Virtual Processing Element and a Thread Context.)

More interesting cases would included decoupled access/execute architectures, GPUs which provide some instruction stream divergence, and a traditional ISA that internally (microarchitecturally) uses speculative multithreading.

Decoupled access/execute architectures have two *partially independent* instruction streams, one performing memory accesses and address calculations, the other performing computation, e.g., see James E. Smith, "Decoupled Access/Execute Computer Architectures" (PDF, so they are not neatly classified as having a single instruction stream but they do not have the extent of independent instruction flow associated with Flynn's Multiple Instruction classifications.

Similarly, some GPUs support some control diverge (different instruction streams applied to different data), which is conceptually similar to applying eager execution (where multiple conditional paths are executed in parallel and only the results of the correct path are committed) to multiple data (where at least one of the data elements unconditionally does follow that execution path). This type of architecture is sometimes called Single Program Multiple Thread or Single Instruction stream Multiple Thread. (Note that GPUs also commonly support more traditional MIMD multithreading.)

Hardware speculative multithreading presents the interface of a single instruction stream, but such uses a microarchitecture that supports multiple partially independent instruction streams. For example, loops might have iterations distributed across multiple threads and function calls might spawn a separate thread while processing continues at the return point (possibly using a predicted return value). Like GPUs and decoupled access/execute, this provides limited independence among instruction streams, but even MIMD programs often have limited independence, synchronizing instruction streams at join points. However, unlike those architectures, hardware speculative multithreading provides a SISD interface to software, so from the programmer's perspective it is SISD while from the hardware perspective it is more like MIMD.

---
Tags: computer-architecture
---


title: Are regular grammars always LR(1)

text:
# Question
Title: Are regular grammars always LR(1)
The question is fairly straight forward. I just found a question on the internet that asks whether all regular grammars are

1. LL(1)
2. LR(1)

I guess they can't be LL(1) because of left recursion, but how do we prove that they are LR(1) if so.

# Answer
No.

LR(k) grammars have to be *unambiguous*, that is there can be only one possible parse tree for every (valid) input. There are left- and right-regular grammars violating that, for example

$\displaystyle\qquad S \to aS \mid aaS \mid a$

or, if that one does not match your definition of right-regular,

$\qquad\displaystyle\begin{align} S &\to aS, S \to aA, \\ A &\to aA, A \to a \end{align}$

as reinierpost mentions in a comment.

Of course, every regular language *does* have an unambiguous (right-)regular grammar; get one from its minimal DFA using the standard construction.
> 2 votes

---
Tags: context-free, parsers
---


title: Understanding the definition of SPMD

text:
# Question
Title: Understanding the definition of SPMD
From Wikipedia

> SPMD (single program, multiple data) is a technique employed to achieve parallelism; it is a subcategory of MIMD. **Tasks are split up and run simultaneously on multiple processors with different input** in order to obtain results faster.

1. Does a program running on SPMD runs as either multiple processes or a process with multiple threads? If former, are the multiple processes runs the same program?
2. Wikipedia tries to compare SPMD with SIMD:

> In SPMD, multiple autonomous processors **simultaneously** execute the same program **at independent points**, rather than in **the lockstep that SIMD imposes on different data**. With SPMD, tasks can be executed on general purpose CPUs; SIMD requires vector processors to manipulate data streams. Note that the two are not mutually exclusive.

What does "at independent points" mean? Does point means time? If yes, isn't "at independent points" contradict "simultaneously"?
3. Wikipedia also compares SPMD with SMP:

> Unlike SPMD, **shared memory multiprocessing, also called symmetric multiprocessing or SMP**, presents the programmer with a common memory space and the possibility to parallelize execution by **having the program take different paths on different processors**. The program starts executing on one processor and the execution splits in a parallel region, which is started when parallel directives are encountered. In a parallel region, the processors execute a single program on different data. A typical example is the parallel DO loop, where different processors work on separate parts of the arrays involved in the loop. At the end of the loop, execution is synchronized, only one processor continues, and the others wait. **The current standard interface for shared memory multiprocessing is OpenMP**. It is usually implemented by lightweight processes, called threads.

From Section 6.3 of *Computer Organization and Design, Fifth Edition: The Hardware/Software interface by David A. Patterson, John L. Hennessy*:

> programmers normally write a single program that runs on all processors of an MIMD computer, **relying on conditional statements when different processors should execute different sections of code**. This style is called Single Program Multiple Data (SPMD), but it is just the normal way to program a MIMD computer.

I don't quite understand how SPMD and SMP are different as stated in Wikipedia, and maybe some paraphrasing may help? In particular, Wikipedia says in SMP, a program can take different paths on different processors. In Patterson's book, in SPMD, a program can also run different sections of code on different processors.

Wikipedia says "The current standard interface for shared memory multiprocessing is OpenMP". Is multithreading by OpenMP or PThread on multiple processors SPMD or SMP?

Thanks.

# Answer
> 5 votes
You are taking these definitions too literally (as if they were mathematical definitions that could be used in a proof.) These terms all come from the "heroic" age of computer architecture when people were designing by the "seat of their pants" and kind of just getting a feel for what works and what doesn't. Treat them more like terms for writing poetry than mathematics.

1. a. SPMD might refer to either multiple threads sharing an address space or multiple processes with independent address spaces sharing only through message passing or through the file system.

b. Typically with SPMD in an environment with separate processes each process would be loaded from the same executable file.
2. Each thread (or process) in a SPMD machine has its own instruction pointer (indicating what instruction should be executed next). Each thread in a SPMD program updates its instruction pointer *independently*. So the threads in a SPMD program execute simultaneously, but they are executing different instructions and there is no required correlation between the instructions those threads are executing.

In a SIMD program there is only *one* instruction pointer. On every time step every execution unit is executing the same instruction simultaneously. (The term NVidia uses for SIMD execution unit is "core", the term most other people use is "vector lane.")
3. a. SMP is not part of Flynn's taxonomy. Flynn's taxonomy is SISD, SIMD, MISD, MIMD. That's it. "SPMD" is something that someone made up after the fact but is the same thing as MIMD (as pointed out by the Hennessy and Patterson quote you include.) "SMP" is part of a completely different poem. It might be best to think of SMP as a particular way of implementing SPMD computers. SMP typically stands for "Symmetric Multiprocess*or*" not "Symmetric Multiprocess*ing*".

b. Multithreading by OpenMP or Pthreads on multiple processors is SPMD (because you are running multiple independent threads on the same program executable.) You might use a SMP to execute your SPMD OpenMP or Pthreads program, or you might use some other implementation of SPMD.

---
Tags: computer-architecture, parallel-computing
---


title: Why is Radix Sort $O(n)$?

text:
# Question
Title: Why is Radix Sort $O(n)$?
In radix sort we first sort by least significant digit then we sort by second least significant digit and so on and end up with sorted list.

Now if we have list of $n$ numbers we need $\log n$ bits to distinguish between those number. So number of radix sort passes we make will be $\log n$. Each pass takes $O(n)$ time and hence running time of radix sort is $O(n \log n)$

But it is well known that it is linear time algorithm. Why?

# Answer
> 22 votes
> if we have a list of $n$ numbers we need $\log n$ bits

No: if we have a list of numbers between $0$ and $2^k - 1$, we need $k$ bits. There is no relationship between $k$ and $\log n$ in general.

If the numbers are all distinct, then $\log n \le k$, and radix sort on distinct numbers therefore has a time complexity of $\Omega(n \log n)$. In general, the complexity of radix sort is $\Theta(n \\, k)$ where $n$ is the number of elements to sort and $k$ is the number of bits in each element.

To say that the complexity of radix sort is $O(n)$ means taking a fixed bit size for the numbers. This implies that for large enough $n$, there will be many duplicate values.

---

There is a general theorem that an array or list sorting method that works by comparing two elements at a time cannot run faster than $\Theta(n \log n)$ in the worst case. Radix sort doesn't work by comparing elements, but the same proof method works. Radix sort is a decision process to determine which permutation to apply to the array; there are $n!$ permutations of the array, and radix sort takes binary decisions, i.e. it decides whether to swap two elements or not at each stage. After $m$ binary decisions, radix sort can decide between $2^m$ permutations. To reach all $n!$ possible permutations, it is necessary that $m \ge \log (n!) = \Theta(n \log n)$.

An assumption in the proof that I did not write out above is that the algorithm must work in the case when the elements are distinct. If it is known a priori that the elements are not all distinct, then the number of potential permutations is less than the full $n!$. When sorting $k$-bit numbers, it is only possible to have $n$ distinct elements when $n \le 2^k$; in that case, the complexity of radix sort is indeed $\Omega(n \log n)$. For larger values of $n$, there must be collisions, which explains how radix sort can have a complexity that's less than $\Theta(n \log n)$ when $n \gt 2^k$.

# Answer
> 10 votes
Be careful with your analysis: what do you assume to make sorting run in $O(n)$ time? This is because each of your digits are in a range from $0$ to $k-1$, meaning your digits can take on $k$ possible values. You need a stable sorting algorithm, so you can for example choose counting sort. Counting sort runs in $\Theta(n+k)$ time. If $k=O(n)$, counting sort runs in linear time.

Each one of your strings or numbers have $d$-digits. As you say, you make $d$ passes over them. Hence, radix sort clearly runs in $\Theta(d(n+k))$ time. But if we consider $d$ to be constant and $k=O(n)$, we see that radix sort runs in linear time.

# Answer
> -2 votes
I think the assumption $k = \log\_2(n)$ is wrong. You can perform radix sort with numbers in, e.g., hex. Thus, at each step you split you array of numbers into $16$ buckets.

---
Tags: algorithms, sorting
---


# Question
Title: Is this combinatorial optimisation problem similar to any known problem?
The problem is as follows:

We have a two dimensional array/grid of numbers, each representing some "benefit" or "profit." We also have two fixed integers $w$ and $h$ (for "width" and "height".) And a fixed integer $n$.

We now wish to overlay $n$ rectangles of dimensions $w \times h$ on the grid such that the total sum of the values of cells in these rectangles is maximized.

The following picture is an example of a two-dimensional grid with two such rectangles overlayed on it (the picture does not demonstrate the optimal solution, just one possible overlaying where $w = h = 2$ and $n = 2$)

The rectangles cannot intersect (otherwise we would just need to find the optimal position for one rectangle and then put all the rectangles in that position.)

In the example above the total sum of values in cells would be $-2 + 4.2 + 2.4 + 3.14 + 2.3 -1.4 + 1 - 3.1$

**Is this similar to any known problem in combinatorial optimisation? so that I can start doing some reading and try to find ways to solve it.**

Some more background for those interested:

So far the only ideas I had are either a greedy algorithm (which would find the best location for the first rectangle, then find the non-overlapping loctaion for the second rectangle etc.) or some metaheuristic such as genetic algorithms.

In reality I wish to solve this problem with a grid which has around a million cells and tens of thousand (or even hundreds of thousands) of rectangles, though it is not necessary to solve it in a short time (i.e it would be acceptable for the algorithm to take hours or even days.) I am not expecting an exact solution but I want to get one which is as good as possible given these constraints.

Cheers!

# Answer
> 2 votes
My last formulation had a fatal flaw that would require an exponential amount of "constraint" nodes.

Another natural graphical formulation of the problem would be to create a graph where each vertex $r$ represents a rectangle with $w\_r$. Any pair of overlapping rectangles $r, r'$ have an edge in this graph. By solving for maximum-weighted independent set of size $k=n$ we have a solution to your original problem. There exist many good heuristics and approximation algorithms for this.

# Answer
> 2 votes
You could formulate this as a gigantic integer linear programming (ILP) instance, and then apply an off-the-shelf ILP solver (lp\_solve, CPLEX, etc.). They will give you the best solution they can find. Given the size of your problem instance, I don't know whether this will be efficient enough, but it would be easy to try.

Here's the ILP formulation. We have a zero-or-one variable $x\_r$ for each possible rectangle $r$, with the intended interpretation that $x\_r=1$ means you include rectangle $r$ in your set and $x\_r=0$ means you don't include it. You want to maximize the objective function $\sum\_r c\_r x\_r$ (where $c\_r$ is the profit of rectangle $r$), subject to the restriction that $\sum\_r x\_r = n$ and that no two rectangles overlap. The latter restriction can be expressed as a linear inequality by requiring $x\_r + x\_s \le 1$ for all pairs of rectangles $r,s$ that overlap. So, in this way you get a ILP.

---
Tags: algorithms, optimization, combinatorics, approximation
---


title: Interactive Proofs for coNP

text:
# Question
Title: Interactive Proofs for coNP
I am trying to understand interactive proof systems and tried the following problem as an exercise. We know that $PH \subseteq PSPACE$ and $IP=PSPACE$, so come up with (easy to understand) interactive proof systems for $PH$?

An interactive proof system for $NP$ is trivial, but I failed to get an interactive proof system even for $coNP$. Do you know of an explicit interactive proof system (by explicit I mean without going through the $IP=PSPACE$ route) for $coNP$?

# Answer
Wikipedia outlines such an example. Consider the coNP-complete problem UNSAT: given a CNF $\varphi$ on $n$ variables, we want to convince the verifier that $\varphi$ is not satisfiable. We arithmetize $\varphi$ to a polynomial $p$ and choose some large prime $q$. Let $$p(x\_1,\ldots,x\_k) = \sum\_{x\_{k+1}=0}^1 \cdots \sum\_{x\_n=0}^1 p(x\_1,\ldots,x\_n).$$ The protocol proceeds as follows:

1. Prover sends verifier a prime $q \in (2^n,2^{n+1})$, and the latter verifies that $q$ is prime.
2. Prover sends verifier $p(z) \in \mathbb{Z}\_q\[z\]$. Verifier verifies that $p(0) + p(1) = 0$, and sends prover a random $r\_1$.
3. Prover sends verifier $p(r\_1,z) \in \mathbb{Z}\_q\[z\]$. Verifier verifies that $p(r\_1,0) + p(r\_1,1) = p(r\_1)$, and sends prover a random $r\_2$.
4. Eventually, verifier gets $p(r\_1,\ldots,r\_n) \in \mathbb{Z}\_q$, and verifies that it has the correct value by evaluating $p$ directly.

Because the degree of $p$ is small compared to $q$, if the prover is cheating then the verifier will probably catch her (see Wikipedia for the proof, or work it out yourself using the Schwartz-Zippel lemma).
> 9 votes

# Answer
Graph non-isomorphism at Proofs that Yield Nothing But their Validity or All Languages in NP have Zero-Knowledge Proofs, Goldreich, Micali and Wigderson, JACM, 1991.

Common input is a pair of graphs: $G\_1, G\_2$. At the start of each round, verifying party chooses an index $i \in \\{1,2\\}$ at random and sends a random permutation of graph $G\_i$. Proving party responds with an index $b \in \\{1,2\\}$.

Completeness property: for non-isomorphic graphs, prover always give correct response $b=i$.

Soundness: for isomorphic graphs, prover give correct response with probability $\frac{1}{2}$.
> -1 votes

---
Tags: complexity-theory, interactive-proof-systems
---


# Question
Title: Relaxation of the null production restriction in Regular and Context Free Grammars
I am convinced of the fact that allowing productions of the form $S \rightarrow \epsilon$ in a context sensitive grammar would allow RE languages to be expressed if $S$ were on the right hand side of some production.

However, in most definitions of regular and context-free grammars (such as those on Wikipedia), this restriction is nowhere to be seen (as an exception, the restriction *is* mentioned in the article on the Chomsky hierarchy for Type-3 languages).

1. Is this relaxation intentional in that both variants (with and without the restriction) have the same expressive power, or is this just a "sloppy" definition?
2. Even if they *do* have the same expressive power, wouldn't that ensure that Context Free Grammars are not a subset of Context Sensitive Grammars, thus violating Chomsky's Hierarchy?

# Answer
> 1 votes
True.

For CFG we can remove in fact all epsilon rules and obtain the same family of languages, except for the empty word. That can be added by adding the $S\to\varepsilon$ production. It is a so-called normal form.

Like Raphael says: it all depends on what you want to express in the formalism, and what makes proofs convenient.

The definition on type-3 grammars is a matter of taste. I would prefer $A\to\varepsilon$, $A\to aB$ as these two types of productions correspond to final states and transitions in finite state automata.

---
Tags: formal-languages, context-free, regular-languages, formal-grammars
---


# Question
Title: How can I fill bookcases with shelves of books using the least number of bookcases?
Sorry for layman's term question, my background in computer science is weak.

What I have is a list of shelves with books of varying height. Each shelf stores a value that describes how many shelves (of that height) can fit on a bookcase. The bookcases have adjustable shelves so that we can maximize the usage of each one.

What I have been trying so far is sorting the shelves from shortest to tallest and filling in each bookcase, but what happens is that there are remainders which could be filled in with the small shelves.

I should mention that an additional complexity is that we want to place the tallest shelf on the top of the bookcase (because it would be more efficient).

I am not expecting a full on answer for how to do this... but I would very much appreciate a book or article on the topic. I just need a little direction and I think I would be able to pick it up.

Thanks for your help!

# Answer
> 3 votes
I'm not clear on whether you have one bookcase or multiple bookcases, so I'll explain how to handle both cases below.

## Multiple bookcases

If you have multiple bookcases, and you need to put each shelf into exactly one of the bookcases, then you have an instance of the bin packing problem.

Each shelf corresponds to an item, and each bookcase corresponds to a bin. Now you want to find a way to put each item into one bin, i.e., put each shelf into one bookcase, so that every shelf is in some bookcase, and each bookcase has room for all the shelves that will go into it.

This can be modelled in a straightforward way as a bin packing problem:

* The "size" of a shelf (an item) is the height of the shelf.
* The "size" of a bookcase (i.e., of a bin) is the height of the bookcase.

Now you want to find a way to assign each shelf to one of the bookcases, so that the sum of the sizes (heights) of the shelves in each bookcase does not exceed the size (height) of the bookcase. That is exactly the bin packing problem.

You should be able to use any standard algorithm for bin packing to solve your problem. Given the number of bookcases and shelves you're likely to have in practice, any of them should be efficient enough for practical use. For instance, one approach is to formulate this as an instance of ILP (integer linear programming), as described in the Wikipedia article on bin packing, and then solve the problem using an off-the-shelf ILP solver, such as lp\_solve or CPLEX. This will likely be very effective in practice.

All of these algorithms can accommodate the requirement to put the tallest shelf on the top: you select the set of shelves to go into each bookcase, and then for each bookcase, find the tallest of the shelves that are going into that bookcase and put it at the top of the bookcase.

## One bookcase

If you have one bookcase, and you can select some subset of the shelves to fill the bookcase, your problem is an instance of the knapsack problem.

Treat each shelf as an item that can be placed into the knapsack. Then:

* the "weight" of a shelf is its height,
* the "value" of a shelf is the value of including that shelf in the bookcase (e.g., the number of books it'll enable you to store, or maybe just a fixed value that's the same for all shelves), and
* the "capacity" of the knapsack is the total height of the bookcase.

The optimal solution to the knapsack problem will select a subset of items whose total weight doesn't exceed the knapsack's capacity, and that maximizes the sum of the values of the selected items.

In your context, that amounts to selecting a subset of the shelves whose total height doesn't exceed the height of the bookcase (and thus it'll be possible to fit all of the selected shelves into your bookcase), and that maximizes the sum of the values of the shelves (e.g., maximizes the total number of shelves that you fit into the bookcase, or the total number of books you can store in the bookcase, etc.).

There are many algorithms for the knapsack problem, such as the dynamic programming algorithm. In your situation, I suspect the number of candidate shelves is small enough that any of these algorithms is likely to be efficient enough for real-world use.

All of these algorithms can accommodate the requirement to put the tallest shelf on the top: you select the set of shelves to go into the bookcase, and then choose the one that is tallest and put it at the top of the bookcase.

---
Tags: optimization, heuristics, packing
---


# Question
Title: How do I build a read/write 4-nibble RAM memory system using flip flops?
Currently, I'm learning about flip flops and how it is used in RAM to store memory so I'm trying to recreate the circuitry in Logisim. I know the components I need which are address register, 4-bit data register, 1 bit read/write register and the actual 4 nibble RAM with its own address space and data space. How do I create each individual pieces and put them together?

# Answer
> 1 votes
You need to put multiplexers and selector/decoders around your flipflops.

The read path needs to multiplex each nibble using the 2 address line.

The write path is selecting with these two address lines with nibble should be modified.

---
Tags: computer-architecture, circuits, memory-hardware, memory-access
---


# Question
Title: Finding set of disjoint sets with additional value optimization
I've got a set $Q$ of pairs $\[S, v\]$ where $S$ is a nonempty set and $v$ is a value ($v \in \mathbb{N}\_{+}$). I need to find a subset $R$ of $Q$ with following properties:

* Sum of all $v$'s is maximum
* $S$ from all pairs construct a disjoint set

Example. For given set $Q$:

$Q = \\{\[\\{1, 2\\}, 5\], \[\\{2, 3\\}, 8\], \[\\{3, 4\\}, 2\], \[\\{5\\}, 1\]\\}$

Result $R$ should be:

$R = \\{\[\\{2, 3\\}, 8\], \[\\{5\\}, 1\]\\}$

I came up with an obvious algorithm which constructs every possible set of pairs whose $S$ constructs disjoint set:

```
T = {}
foreach (q in Q)
  foreach (t in T)
    if (union of all S from t and S from q constructs a disjoint set)
      add copy of t to T
      add q to t
  add {q} to T

```

Then I would find `t` with highest sum of all it's `v`'s.

This is worst case $O(2^n)$. Can I do better than this? I will appreciate any additional information regarding this problem.

# Answer
> 3 votes
Your problem is polynomially equivalent to the maximum-weight independent set problem problem, and the standard results for that problem apply directly to your problem as well.

If all the values were the same (say, $v=1$ for all pairs), then your problem would equivalent to the independent set problem. In particular, treat each pair as its own vertex, and build an undirected graph $G$ where you have an edge between two pairs if they are disjoint. Then the solution to your problem is exactly the largest independent set in $G$. One can also construct a reduction the other way as well: given any undirected graph $G$, we can form an instance of your problem by construct a set corresponding to each vertex of $G$ (namely, the set of edges incident on that vertex), each of value 1; then the solution to your problem is the maximum independent set of $G$.

The independent set problem is NP-complete, so it follows that your problem is NP-complete as well. Therefore, you should not expect any polynomial-time solution to your problem.

Because you allow arbitrary values to be associated with each set, your problem is basically equivalent to a slight generalization of the independent set problem, namely, the maximum-weight independent set problem. Each vertex has a weight associated with it, and the weight of an independent set is the sum of the weights of the vertices in the independent set, and the problem is to find the heaviest independent set in the graph. This is obviously at least as hard as the standard independent set problem, so also NP-complete.

Fortunately, there are standard algorithms for the independent set problem, and they can be extended to the maximum-weight independent set problem as well. For instance, you can formulate the problem as an integer linear programming (ILP) instance and then try to solve it using an off-the-shelf ILP solver. There are also exponential-time algorithms for independent set whose running time is asymptotically faster than $\Theta(2^n)$; I don't know whether they extend to the maximum-weight independent set problem as well, but you could check the literature to see, if this is of interest. You could try applying them to your problem.

Unfortunately, the independent set problem is known to be hard to approximate to within a constant factor (unless P = NP), so you should not expect efficient approximation algorithms for your problem, either.

---
Tags: optimization, sets
---


# Question
Title: Understanding Decision Stump in Adaboost
I am trying to understand how Adaboost works, and many of the tutorials online involve the use of a decision tree stump. For example, http://www.cc.gatech.edu/~thad/6601-gradAI-fall2013/boosting.pdf or http://www.fromdev.com/2012/04/creating-weak-learner-with-decision.html. However, I am confused on how the plot is actually generated. Say I have the following training set:

```
               Event 1     Event 2     Event 3
Classifier 1      -1          1          1
Classifier 2      1           -1         1
Classifier 3      1           1          -1

```

How should I generate a decision stump for this?

# Answer
> -1 votes
I wonder if you what decision stump is.

Decision stump is simply a decision tree with only one node. It is usually considered as the weak classifier in boosting algorithms since due to its simplicity it will not overfit.

In your question it is not clear what is even 1 .. 3. Anyhow, the classifiers can be : decision stump1, decision stump2 and decision stump3.

---
Tags: artificial-intelligence
---


title: Basic linear programming question

text:
# Question
Title: Basic linear programming question
Trying to answer this question:

*A factory produces chocolate and candy. In order to produce 100 kilograms of chocolate, the factory has to use machine A for 1 hour, machine B for 4 hours, and machine C for 2 hours. In order to produce 100 kilograms of candy, the factory has to use machine A for 2 hours, machine B for 1 hour, and machine C for 1 hour. The factory will earn 5 pounds for each kilogram of chocolate it produces and 3 pounds for each kilogram of candy it produces. Machine A and machine B belong to the factory and can be run for free 24 hours a day. However machine C is rented from a different company and can only be run up to 16 hours a day and costs 20 pounds for each hour it is run. Write down an LP model to maximize the factory profit per day. Explain what each of the variables in the LP formulation means.*

Initially I had

$max z = 5x\_1 + 3x\_2$

$x\_1 + 2x\_2 \leq 24$ // machine A

$4x\_1 + x\_2 \leq 24$ // machine B

$2x\_1 + x\_2 \leq 16$ // machine B

$x\_1, x\_2, x\_3 \geq 0$

However, I then realised that machine C costs £20 for every hour it is used, which affects the objective function. Been looking at this for a while and still can't figure out how to formulate this, any ideas? Would be highly appreciated.

edit: Should the objective function have something like $-20x\_3$ at the end? Where $x\_3$ is the number of hours machine C runs for

# Answer
> 1 votes
Suggestions:

### Varaibles:

introducing a dummy varaible $t$.

### Objective function:

add term $-20t $ to the function

### Constraints:

Replacing the last constraint w.r.t. Machine C with \begin{align} t \leq 16 \\ 2x\_1 + 1x\_2 \leq t \\ t\geq 0. \end{align} Done !

---
Tags: linear-programming
---


title: Complexity of Simon's Problem

text:
# Question
Title: Complexity of Simon's Problem
In reading the Wiki article on Simon's Problem, the article states that it takes exponential time(in the classical version) to discover the secret string S that is inside the black box. Why is this black box problem not considered to be a one way function and are there any cryptographic primitives based on the hardness of discovering the secret string S. Thank you!

# Answer
> 1 votes
A one-way function is a function $f$ such that $f(x)$ is easy to compute, but given $y$ in the range of $f$, it is hard to computer a preimage of $f$. Notice that there is no black-box involved. The idea is that $f$ "looks like" a black box that applies $f$ in the sense that you can apply $f$ but cannot do much more, and in particular cannot invert $f$ (or even learn anything about the inverse).

The goal of cryptography is to come up with cryptographically secure algorithms. There is no place for a black box there. That said, when constructing protocols from primitives, we often treat the primitives as black boxes with certain properties. In some cases we can actually show that this point of view isn't general enough - we show that given one primitive as a black box, another primitive cannot be constructed, though perhaps such a construction is possible given access to the code of the first primitive.

---
Tags: complexity-theory
---


# Question
Title: Probability of having a log(n) length monotone subsequence in a random permutation of {1,...,n}
How can I compute the probability of having a $\log(n)$ length monotone consecutive subsequence in a random permutation of $\\{1,...,n\\}$.

I wish to upperbound it with $1/n$.

# Answer
> 1 votes
You can upper bound this probability as follows. The relative order within a consecutive subsequence of a random permutation is just another random permutation, so the probability that a specific consecutive subsequence of length $\log n$ is monotone is exactly $2/(\log n )!$. Since there are at most $n$ of this (actually, exactly $n-\log n+1$), the probability is at most $$ \frac{2n}{(\log n)!} \sim \frac{2n}{\sqrt{2\pi\log n}(\log n/e)^{\log n}} = o\left(\frac{1}{n}\right). $$

---
Tags: combinatorics, probabilistic-algorithms, permutations
---


title: Is this problem P or NP?

text:
# Question
Title: Is this problem P or NP?
Given a set of whole numbers $M=\\{z\_0, ..., z\_n\\}$ Are there $z\_i$ and $z\_j$ with $i \neq j$ but $z\_i = z\_j$?

Is this Problem (surely or only probably) in $P$ or in $NP$? Is it $NP-hard$?

# Answer
This is the *element distinctness* problem, and can be solved in polynomial time in many ways. For example, you can go over all pairs of elements and compare them, or if the elements are comparable, you can sort them and then check for duplicate elements (though in principle comparisons could be very time consuming, and in that case potentially the algorithms wouldn't be polynomial time; there's no such problem with the former algorithm).

Make sure you understand what "polynomial time" is. Also, you have a false dichotomy in your title: every problem in P is also in NP; if P=NP then every problem in P is also NP-complete; and if P≠NP then there are problems which are neither in P nor NP-hard.
> 2 votes

---
Tags: algorithms, complexity-theory, time-complexity, np-hard, np
---


# Question
Title: Closure properties between 2 languages of different types
Whenever said - The intersection between a Context Free Language and a Regular Language is always Context Free, what is the best logical way to confirm the statement?
I have this Chomsky hierarchy in mind that I refer whenever closure properties between **Type-m** and **Type-n** languages are asked but sometimes I come up with a wrong result.
How do you people logically solve it? What is the best simplest way?

# Answer
You have to *prove* that the intersection of a context-free language and a regular language is always context-free. The simplest proof might go through push-down automata. Given a push-down automaton for a context-free language $L\_1$, it is not too hard to augment it so that the state of a DFA for the regular language $L\_2$ is maintained, and given this, you can construct a push-down automaton for $L\_1\cap L\_2$. Other proofs are also possible.

Each such question should be considered on its own. There are no general tricks. You can't just rely on the diagram. The problem with relying on the diagram in this case is that the intersection of two context-free languages need not be context-free; so the fact that regular languages are context-free isn't enough to show that the intersection of a context-free language and a regular language is again context-free.
> 3 votes

---
Tags: formal-languages, context-free, regular-languages, finite-automata
---


# Question
Title: Prove by Induction that $r_n$ is $O(\log_2(\log_2n))$
Let the sequence $r$ be defined by:

$$\begin{align\*}r\_{1} &= 1\\ r\_n&= 1 + r\_{\lfloor\sqrt{n}\rfloor}\\,,\quad n\geq 2\\,.\end{align\*}$$

Prove by induction that $r\_n$ is $O(\log\_2(\log\_2n))$.

My idea is to find the closed form function of r and then use the big O definition on the closed form function but I'm having a hard time even finding the function in the first place. Any help? Also is this even the right way to approach this proof?

Thanks.

# Answer
To prove $r\_n = O(\lg \lg n)$ by induction on $n$, suppose $r\_n \le c (\lg \lg n)$ is true for $n$ and consider $r\_{n+1}$:

$$r\_{n+1} = 1 + r\_{\lfloor \sqrt{n+1} \rfloor} \le 1 + c(\lg \lg (\lfloor \sqrt{n+1} \rfloor)) \le 1 + c(\lg \lg \sqrt{n+1}) \\ = 1 + c(\lg (1/2\lg (n+1)) = 1 + c(-1 + \lg \lg(n+1)) \\ = 1-c + c(\lg \lg (n+1)) $$

Take $c = 1$.

---

If you don't stick to the mathematical induction, there is an easier method with less computation by "change-of-variable" (ignore the things of "taking floor"):

Take $m = \lg n$. Consider another sequence $s$ with $s(m) = r(2^{m})$:

$$r(2^{m}) = 1 + r(2^{m/2}) \Rightarrow s(m) = 1 + s(m/2) = \Theta(\lg m) \quad \text{(by the master theorem)}$$

Substitute $m = \lg n$ into the last equation, we have $r(n) = \Theta(\lg \lg n)$.
> 2 votes

---
Tags: recurrence-relation, induction
---


# Question
Title: Pumping Lemma for Regular Language seems to Fail
Let $L = \\{ab^ncd \mid n \geq 0\\}$. If we take $p = 5$ and $w = abbcd$ and write $w\_i = xy^iz$, where $x = abb$, $y=c$, $z=d$, then $w\_2 = abbccd$ which is not in $L$. We conclude that $L$ is not regular but it obviously is!

What am I doing wrong?

# Answer
The pumping lemma says that *there exists* a decomposition of $w$ to $xyz$ such that $y$ can be pumped.

It doesn't say that *for all* decompositions of $w$ to $xyz$, $y$ can be pumped.

In your example, a possible decomposition is:

$x=a$

$y=bb$

$z=cd$
> 3 votes

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


# Question
Title: Prefix computation used for lexical analysis?
I'm preparing a presentation on prefix computation (aka scan, the generalization of prefix summation to any associative operator) for a class I'm taking on parallel algorithms.

Several lists of applications of prefix computation include lexical analysis (tokenizing), but do not cite a source for that. I have failed to find any other reference to it being used that way.

Where has any description of the use of a prefix computation for the purpose or lexical analysis been published? (Or, what was the origin of this misinformation?)

# Answer
The important fact in this case is that the list `append` operation is associative.

Hadoop has "tokenize" as one of its built-in parallel operators. The meaning of "tokenize" in this case is much less general than "lexical analysis". They mean "splitting a string at a specific well-defined set of \`delimeter' characters." I doubt there is much you could do with a more general lexical analyzer (one where you are running an arbitrary finite-automata over a string.)

So suppose you need to split a string at all the space characters. You are essentially creating a list of indices into the string. The list `append` operation is associative. So each processor generates the appropriate list of indices for the substring assigned to it, and then you append all the lists together.
> 1 votes

---
Tags: reference-request, parallel-computing, applied-theory, lexical-analysis
---


# Question
Title: Term for a matching which is perfect on one side only
What is a standard term for a matching in a bipartite graph, in which one part has less vertices than the other part, and the part with less vertices is fully matched (but the other part is, obviously, not fully matched)?

It is not exactly perfect, but it is "one-sided perfect", or "as perfect as it could be". What is a short term to use for this kind of matching?

# Answer
Such a matching is said to *saturate* one of the sides. More specifically, if $M$ is a matching of a graph $G$ and $v$ is incident to one of the edges of $M$, we say that $M$ saturates $v$. If $A$ is a set of vertices, then we say that $M$ saturates $A$ if every vertex in $A$ is saturated by $M$.

Specifically for your case, the matching saturates the smaller of the two sides of the bipartition.
> 5 votes

---
Tags: graphs, terminology, bipartite-matching
---


title: Solving Recurrence Relations 3

text:
# Question
Title: Solving Recurrence Relations 3
Consider the following recurrence $$T(n)=T(n-1)+n\log n$$

My approach: Solving using Substitution $T(n)=n \log n+(n-1) \log (n-1)+(n-2) \log (n-2)+(n-3) \log (n-3)+...$

$=\[n\log n + n \log(n-1)+ n \log(n-2)+ n \log(n-3)+...\]-\[\log(n-1)+2\log(n-2)+3\log(n-3)+...\]$

$=\[n(\log n + \log(n-1)+ \log(n-2)+ \log(n-3)+...)\]-\[\log(n-1)+2\log(n-2)+3\log(n-3)+...\]$

$=\[n(\log(n(n-1)(n-2)(n-3)+...)\]-\[\log(n-1)+2\log(n-2)+3\log(n-3)+...\]$

$=\[n(\log n!)\]-\[\log(n-1)+2\log(n-2)+3\log(n-3)+...\]$

$\approx O(n^2 \log n)$

But ans is given as $O(n \log n)$. What have I done wrong

# Answer
Your answer is correct. $O(n \log n)$ is wrong. This is easily shown by considering the sum of $j \log j$ over $j=n/2,\dots,n-1,n$; each term is at least $\frac12 n \log (n/2)$, and there are $n/2$ terms, so the total sum is at least $\frac14 n^2 \log(n/2)$, which is $\Theta(n^2 \log n)$.
> 2 votes

---
Tags: recurrence-relation
---


title: Direct Cache Mapping - Addressing

text:
# Question
Title: Direct Cache Mapping - Addressing
I've looked through all the other similar questions, but I don't feel like I understood exactly what I'm supposed to do with my case, so I'm hoping I'm not the only one.

In an exercise I'm doing, I'm told to consider a computational system with a direct mapping cache, that can store 16 blocks of 4 bytes, and 32-bit addresses.

I'm then given 8 addresses in hexadecimal, and I'm supposed to say what will be the content of the 16 blocks.

One of the adresses in question is: 0xC4001234 I've calculated the tag as 21 bits, set being 4 bits, and offset being 5 bits. Yet, I'm not sure how I'm supposed to know in which block it will be. My teacher's Powerpoint said that the "set" is used to locate the block in the memory, but I'm not sure how. I thought I'd convert the address into binary and use the 4 bits to calculate where the block will be, but then I have some adresses that match in the same block.

I was wondering if anyone could show me how to do this one address, so I can do this exercise and hopefully pass my exam. Thanks.

# Answer
Your cache is direct mapped so there are no sets. Those are set associative caches.

In your example the tag is 26 bit, block 4 bit and byte offset is 2 bit.

To get that just break your 32 bits into tag, block and byte fields. 16 blocks means 4 bits to address a block. 4 byte blocks means 2 bits to address bytes within blocks. Rest of the bits are 26, which is the tag. When you convert 0xC4001234 to binary and remove first 26 bits and the last 2 bits that gives you the 4 block bits.

In your case it is 1101 or block 13 of 0-15.
> 1 votes

---
Tags: computer-architecture, cpu-cache
---


# Question
Title: Memory Requirement for a Computable Problem
I was thinking whether it is true that every computational problem intrinsically has a minimum ammount of memory required for any algorithm that computes it.
But then i was confused to what "memory requirement" really means and how we could quantify it .
Looking for how Computational Complexity treats the memory requirement of a computational problem made me even more confused, because it always consider memory requirement under Turing Machines ... so it really doesnt treat the memory requirement as universal as it could ( applied to any possible model of computation : be it FSM, Lambda Calc, or whatever ).

Let me elaborate on my confusion.

It was intuitively thinking of characterizing the memory requirement of algorithms in terms of levels of memory. For automatas, binary addition of numbers too small so we don't need carriers would be a problem that would require no memory at all .
But addition with carriers and 1-momment delaying would be problems at least 1 level of memory. Binary multiplication of arbitrarily large numbers, however, would require arbitrarily large levels of memory . It's so wierd that Combinational Logic circuits can solve all those problems ( arithmetic with carriers ) if it doesn't have any memory at all ( no flip-flop ). How can we understand that ? Is a combinational logic circuit doing computations ? Can we see it as a weak model of computation ?

I had a hope that Space Complexity in the Computational Complexity discipline cold formalize this idea of "levels of memory, but it seems that since the framework is always Turing Machines, everything requires memory, even a simple addition without carriers ( in fact, it needs memory to simulate combinational logic circuits that are models of computation that don't require memory ) .

But there are many problems with this notion of "levels of memory".

1 - What does a level of memory really mean ? Do we universally have only two ways of encoding those levels of memory : either on the states of a machine , or on auxiliary memory read by a machine.

2 - In case the first question is true, would the correspondence for encoding levels of memory on the states of a machine be : n levels of memory require at least 2^n states ? At least, for Finite State Machines, it seems to be that way .
But what about the correspondence for encoding levels of memory on auxiliary memory ( tape-memory ) read by a machine ?

Anyways, i'm really stuck with this doubt for some time and any clarification ( suggestion of a topic for me to read, or any resource at all , explanations and any insight about that ) on how we can understand treat this memory requiment concept universally would be really helpful.

Thanks a lot in advance.

# Answer
> 1 votes
Yes, there's plenty of theoretical work on space complexity. No, it's not necessarily Turing machines; you can talk about space complexity in other models of computation, e.g., the RAM model. You might find that more practically relevant. I suggest you study RAM machines and existing work on space complexity.

It's not clear what you mean by "levels of memory", and I don't see anything there that's useful. Instead, standard space complexity results talks about the space requirement: e.g., $\Theta(n)$ space, $\Theta(n^2)$ space, $\Theta(2^n)$ space. See also LOGSPACE, PSPACE and similar complexity classes.

---
Tags: algorithms, space-complexity, computation-models
---


# Question
Title: Potential method for dynamic binary search
I'm trying to solve 17-2(b) problem from Cormen(CLRS) using potential method.

Problem from Cormen:

17-2 Making binary search dynamic Binary search of a sorted array takes logarithmic search time, but the time to insert a new element is linear in the size of the array. We can improve the time for insertion by keeping several sorted arrays.

Specifically, suppose that we wish to support SEARCH and INSERT on a set of $n$ elements. Let $k = \lceil \log\_2(n + 1) \rceil$, and let the binary representation of n be $\langle n\_{k-1}, n\_{k-2}, \dots , n\_0 \rangle$. We have $k$ sorted arrays $A\_0, A\_1, \dots, A\_{k - 1}$, where for $i = 0, 1, \dots, k - 1$, the length of array $A\_i$ is $2^i$. Each array is either full or empty, depending on whether $n\_i = 1$ or $n\_i = 0$, respectively. The total number of elements held in all $k$ arrays is therefore $\sum^{k-1}\_{i=0}n\_i 2^i = n$. Although each individual array is sorted, elements in different arrays bear no particular relationship to each other.

* Describe how to perform the SEARCH operation for this data structure. Analyze its worst-case running time.
* Describe how to perform the INSERT operation. Analyze its worst-case and amortized running times.
* Discuss how to implement DELETE.

---

So I'm trying to solve point b. Working time: we have $k = \log\_2(n)$ sorted arrays $A\_i$ and corresponding bits $b\_i$. Size of array $A\_i$ is $2^i$. If it's full then $b\_i = 1$ else $b\_i = 0$.

If first $r$ arrays are full then we can place all elements from them to empty array $A\_r$. And we need $2^{r+1} - 2$ time(we merge first arrays: $2 \cdot (2^0 + 2^1 + \dots + 2^{r-1}) = 2^{r+1} - 2$).

Let potential function be $\Phi\_i = 2^{r+1} - 2$, where r is number of first bits which are 1. For example, if we have bit string 111110110101 then $r=5$. If $r = 0$ then $\Phi\_i = 0$.

Now suppose that we want to calculate amortized cost $\hat{c}\_i$ when first $r \> 0$ bits are 1. Thus, $\hat{c}\_i = 2^{r+1} - 2 + (0 - (2^{r+1} - 2)) = 0$

If $r = 0$ then $\hat{c}\_i = 3$.

So we can insert $n$ elements for $\mathcal{O}(n)$ time and they will be sorted. But this is contradicts to lower bound of compare-based sorting.

Could you please help me to find a mistake in my reasoning. I know that correct amortized time is $\hat{c}\_i = \mathcal{O}(\log\_2(n))$ if we use account method(I found the solution).

Thank you very much!

# Answer
> 2 votes
What about this potential function

$$\Phi = \sum\_{i=0}^{k-1} n\_i \cdot 2^i \cdot \left((k-1) - i \right),$$

where $k = \lceil \lg(n+1) \rceil$ (*please check the details related to the stuff of $\lg$ and $\lceil \rceil$*).

That is, each element in *"depth"* $n\_i (i = 0, \cdots, k-1)$ has its "individual potential" $(k-1) - i$. The intuition is the higher the element is, the more potential it has and the higher price you pay to move it down (until the bottom). The whole potential of the data structure at any state is the sum of the potential of its all elements.

With this potential function, the amortized cost for the insertion of an element which *does not cause any merge* (i.e., the element is inserted into the empty subarray $A\_0$) is

$$\hat{c} = 1 \quad (\text{actual cost for creation}) + (k-1) \quad (\text{increment of the potential function}) \\ = k = \lceil \lg(n+1) \rceil.$$

On the other hand, the amortized cost for the insertion of an element which *causes $t$ merges* is (*please check the computation*):

$$\hat{c} = 1 + \sum\_{i=1}^{t} 2^t - (\sum\_{i=0}^{i=t-1} 2^i (t-i)) \quad (\text{the potential decreases}) \\ = (2^{t+1} - 1) - (t(2^t-1) - (2^t t-2^{t+1} +2)) \\ = t + 1 \le k = \lceil \lg(n+1) \rceil.$$

Therefore, the amortized cost for each insertion is $O(\lg n)$.

---

Explanation for the decrement of the potential function $\sum\_{i=0}^{i=t-1} 2^i (t-i)$:
First, each subarray $A\_i,i=0,⋯,t−1$ contains $2^i$ elements. Secondly, each element in $A\_i$ will be moved down to the $t$-th level subarray $A\_t$, decreasing its potential by $t−i$, i.e., from $(k−1)−i$ to $(k−1)−t$. Summing them up, we obtain the total decrement of the potential function.

---
Tags: amortized-analysis, binary-search
---


# Question
Title: Language consisting of all Turing machine encodings
$A=${$ ⟨M⟩$:$M$ $is$ $a$ $Turing$ $Machine$ }

What can be said about $A$ ? Specifically, is $A$ decidable,regular,CFL,CSL?

I would say $A$ is decidable since we can write an algorithm to check whether a string is a valid encoding of a Turing machine .

But, is $A$ Regular\[or CFL or CSL\] ?

Edit : Someone argued that he could make an encoding where all the possible strings(What would be the alphabet here?-same as the encoding I suppose) are valid encoding of a TM(since there is a one-to-one correspondence between two countable infinite sets), hence making $A$ regular .

# Answer
> 3 votes
The complexity of $A$ depends on the encoding used for Turing machines. It is easy to come up with an encoding in which *every* string encodes some Turing machine (there are lots of ways). In contrast, it is easy to come up with artificially "hard" encodings, say the $k$th Turing machine being encoded by $1^kb$, where $b=1$ iff the $k$th Turing machine halts on the empty input; under this encoding, $A$ is not decidable. Nevertheless, it seems intuitively clear that any *reasonable* encoding makes $A$ decidable, though it's hard to say anything more without knowing the exact encoding.

---
Tags: formal-languages, computability, turing-machines
---


# Question
Title: Combinational Logic Circuits and Theory of Computation
I'm trying to link Combinational Logic Circuits ( computers based on logical gates only ) with everything I have learned recently in Theory of Computation.

I was wondering whether combinational logic circuits can implement computations in the same way finite state machines can. They seem radically different :

Finite State Machines, however, have a well-defined memory in the form of the states that it can be in. Combinational logic circuits, however, don't have a well-defined memory so to implement algorithms that need memory they kinda use some weird method of serial connection ( see how $C\_{out}$ of previous adder is connected to $C\_{in}$ of current adder in the image bellow ) .

However radically different might seem, they both seems to be doing computations. For instance, both can implement an algorithm for binary addition ( and even binary multiplication ) however different those implementations might be :

**FSM :**

**Combinational Logic Circuit** ( C, as in $C\_{in}$ and $C\_{out}$, stands for Carry ) :

I'm even thinking ( although still very uncertain ) that we can convert every FSM into a corresponding Combinational Logic Circuit.

So, i'm asking myself :

Can Combinational Logic Circuits also be considered a instantaneous kind of model of computation ? Can we apply all concepts we learn in Computability Theory and Computational Complexity Theory, like space complexity and computability, to it ?

On one hand, it seems like they don't fit as a model of computation because they don't have elementary operations ( like reading/writing of a tape, function reduction, steps on the proof search of logical programming paradigma ), they implement their computations instantaneously.
But on the other hand, they seem to be fit as a model of computation because we can model all kinds of computation with them ( binary addition is one example ), and they can be viewed abstractly ( by only focusing on the truth-tables and the logical gates and forgetting about the physical circuit that might implement it ).
So, what do you guys think ?

Also, if it can indeed be considered as a (instantaneous kind of ) model of computation, do you guys have any example of other similar ( also a instantaneous kind of ) model of computation ?

Thanks a lot in advance

# Answer
> 12 votes
Logic circuits are common in complexity theory, where they go by the name *circuits*. There is a big difference between circuits and models of computation such as the Turing machine: each circuit can only handle inputs of fixed size. In order to fix this, under the circuit computation model, for every input length $n$ there is a circuit $C\_n$, and together they compute a function on strings of arbitrary length. This computation model, as stated, is too strong: it can compute uncomputable functions, indeed *all* functions. The problem is that an infinite sequence of circuits doesn't necessarily have a finite description. In order to fix this problem, we usually demand that the circuits be *uniform*, that is, that they be generated by some Turing machine, which on input $n$ generates $C\_n$.

The circuit model is especially popular in complexity theory, even without the uniformity restriction. The reason is the following observation: a Turing machine running in polynomial time can be converted to a (uniform) sequence of circuits of polynomial size, using essentially the ideas of Cook's theorem (which shows that SAT is NP-complete). Hence if you want to prove that a certain problem cannot be solved in polynomial time, it is enough to show that it cannot be solved by polynomial size circuits.

---
Tags: complexity-theory, turing-machines, computation-models, circuits
---


# Question
Title: Build Automatic Speech Recognition (ASR) from scratch
I want to build a Automatic Speech Recognition (ASR) engine for myself, but I've no idea from where to start.

I've read that most ASR's are build upon Hidden Markov Models, but also I've read that HMM is limited somehow and a better approach is to build a ASR upon Machine Learning features.

Overall I am confused.

Can someone recommend me books on topics from which I can start?

Thanks (:

# Answer
> I want to build a Automatic Speech Recognition (ASR) engine for myself, but I've no idea from where to start.

Start with trying existing open source speech recognition system, learn how they work, play with them. Check http://cmusphinx.sourceforge.net.

> I've read that most ASR's are build upon Hidden Markov Models, but also I've read that HMM is limited somehow and a better approach is to build a ASR upon Machine Learning features.

HMM which provide time variance is still a reasonable model for speech, most of the system use it in one form or another. Limitations of HMM exist, but you do not need to care about them on that level.

You can implement a basic speech recognition system without HMM. For example check

http://de.mathworks.com/company/newsletters/articles/developing-an-isolated-word-recognition-system-in-matlab.html

That would be enough for "yes" and "no" discrimination. For any more serious use you will need HMM.

> Can someone recommend me books on topics from which I can start?

There are two good books on topic:

A basic guide to start:

http://www.amazon.com/Spoken-Language-Processing-Algorithm-Development/dp/0130226165

A modern state of the art

http://www.amazon.com/Automatic-Speech-Recognition-Communication-Technology/dp/1447157788/
> 3 votes

---
Tags: machine-learning, hidden-markov-models, speech-recognition
---


# Question
Title: What is the implication of NP-completeness if P=NP?
If a certain problem $X$ is NP-complete and $P\neq NP$, then $X$ is not polynomial. But we still don't know that $P\neq NP$, so in theory $X$ may be polynomial. Does the fact that $X$ is NP-complete say anything about it being more difficult than other polynomial problems? In particular:

1. Does it mean that $X$ cannot be solved in linear time? (alternatively, are there NP-complete problems that can be solved in linear time if $P=NP$)?
2. Does it mean that $X$ cannot be solved in quadratic time? (alternatively, are there NP-complete problems that can be solved in quadratic time if $P=NP$)?
3. If $X$ is NP-complete, and I prove a lower bound of $\Omega(n^2)$ on the run time of $X$ (a lower bound that *does not* depend on whether $P=NP$), did I prove anything new?

# Answer
Yes, but without further information, only that $X$ has a lower bound of $\Omega(n^{2})$. (I'm assuming that, in line with the title, you're interested in what happens if it turns out that $P=NP$) The problem with transferring this information elsewhere is with the reductions used. As the only constraint is that they're computable in polynomial time, we can easily have the case that we simply solve the problem as part of the reduction (again assuming $P=NP$), so we can reduce it to any other problem in $P$ (this is why $P$-completeness is defined using more restrictive reductions - $NC$ reductions or logspace reductions, or similar, depending on exactly what version you're going for).

With some more specific information we can say something. If we have a problem $W$ where $X \leq\_{P} W$ and we can compute the reduction in $O(n^{c})$ where $c \< 2$, then we know that $W$ has a lower bound of $\Omega(n^{2/c})$ essentially because an upper bound on the problem tells us something. Say $A$ has an upper bound of $O(n^{c\_1})$ for some $c\_1$, we have a problem $B$ such that $B \leq\_{P} A$ and we can compute this reduction in $O(n^{c\_{2}})$, then $B$ has, at worst, a $O(n^{c\_{1}c\_{2}})$ algorithm - at worst we can convert the instance of $B$ to an instance of $A$ and solve that instead. So in our case, if $W$ had an upper bound of $O(n^{2/c - \varepsilon})$ for any $\varepsilon \> 0$, then $X$ could be solved in $O(n^{c\cdot (2/c - \varepsilon)}) = O(n^{2-c\varepsilon})$, contradicting the lower bound.

Note of course that none of this really has anything to do with $X$ being $NP$-complete, it's true for any problem in $P$.
> 1 votes

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


# Question
Title: How to prove computational completeness of a variant of P system
I have read a lot of books on membrane computing (P system), of which the computational completeness of several variants are already under investigation. My goal is to design my own variant and prove its computational completeness.

I also know that in order to prove computational completeness many research papers normally prove the equivalence of their variants of P system with variants of formal languages (e.g. context-free, context sensitive languages, Turing machines etc.), those of which are already known to be computationally complete.

My question is how exactly can I prove equivalence of a variant of P system with a formal language?

# Answer
When you have studied a lot of papers, as you say, then you must have seen how it works. You prove a system to be computationally complete by showing how your new system is able to simulate a Turing machine. Instead of a Turing machine you can use any computational model that in itself is computationally complete, like counter automata (register machines) for example.

In P system theory there are many variants, some work on strings, other on numbers. The model you choose to simulate ideally must match that domain.

So, you do not use "formal language" as such, but only the models studied by formal language theory.
> 1 votes

---
Tags: computability, turing-machines
---


# Question
Title: An example of a non-regular grammar for a regular language?
I understand that a regular language can be specified by either regular or non-regular grammars. What is an example of a non-regular grammar for a regular language?

# Answer
Regular Language L = {aab}

Non-regular grammar

S -\> aAb

A -\> a
> 5 votes

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


# Question
Title: Looking for an example of proving space upper bounds for computing functions on a DTM
Like think of the function $f\colon \\{ 0,1\\}^\* \rightarrow \\{0,1\\}^\*$ which maps a binary string string $x$ to say a string of $0$s of length $\vert x \vert ^2$ whre $\vert x \vert$ is the length of the input string.

This to my mind looks like a work that can be done using only a linear amount of space on the work tape. All you really need to do is just have a counter to count the length of the input string in one pass and then you know what $\vert x \vert$ is and then squaring it is a constant time process and then just output those many $0$s.

Is my intutiion correct? How is one supposed to formally prove such a space-bound on the working of a (deterministic Turing Machine) DTM? Can someone kindly show how to write this up formally?

# Answer
> 1 votes
Perhaps the simplest way to show that a certain task can be done with small space is writing C-like pseudocode for it. If you are only using a constant number of variables, and each variable is exponentially bounded in terms of the input length (i.e. $|x| = O(k^n)$ for fixed $k$), then the resulting computation uses at most linear space. You can use the fact that addition, multiplication and division can be done in linear space ($O(n)$), as well as operations like determining the input length.

As an example, here is pseudocode for your algorithm:

```
f(x) {
  l = |x|;
  y = l * l;
  for i from 1 to y do:
    output 0;
}

```

The variables here are $l,y,i$ ($x$ is on the input tape so doesn't count). All operations are in linear space (as long as the inputs are small enough), $l \leq n$ and $y,i \leq n^2$, so the algorithm uses linear space.

If the bounds on the variables are polynomial ($O(n^k)$) rather than exponential ($O(k^n)$), then the resulting program is logspace (uses $O(\log n)$ space); all operations mentioned can be implemented in logspace. Indeed, since the bounds in your case are polynomial, your algorithm *is* logspace; the fact that the output is larger doesn't matter, since we only count space on the work tape.

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


# Question
Title: Proving L = {$ { a^{2^n} \ | \ n \ge 0 } $} is not regular by use of Pumping Lemma
I've been struggling with this problem for quite a while now and every explanation I have managed to find doesn't seem to correctly solve it.

We have the language L = {$ { a^{2^n} \ | \ n \ge 0 } $} and we need to prove that it is not regular by use of the pumping lemma.

(i.e. L is words whose length is a power of 2: a, aa, aaaa, aaaaaaaa etc.)

I appreciate the concept of the proof so here we go:

Assuming regularity of L and using the Pumping Lemma, we have $ {a^{2^p}} = {xyz}$ where:

a) ${|y| \> 0}$

b) ${|xy| \le p}$

c) $xy^iz \in L \ \forall \ i \ge 0$

(also $ |xyz|\ = 2^p \ge p$)

(notice both x and z can be empty)

I choose $ i = 2$ to get $xy^2z$ so (since $y\>0$) $|xy^2z| \> 2^p$

I understand that the next step is trying to prove that $|xy^2z| \< 2^{p+1}$ so that the final result is $2^p \< |xy^2z| \< 2^{p+1}$ and so $xy^2z$ cannot be an element of L.

However if $|y| = p$ and so $|x| = 0,\ |z| = 0$ then this is not possible as taking $y^2$ is just doubling the length of the word which makes another word that fits the language.

Am I missing something important? I have found proofs on multiple web pages (see below) that just seem to assume y cannot be of length p but as far as I can see this isn't the case.

http://cs.geneseo.edu/~baldwin/csci342/fall2012/0928pump.html http://www.cse.buffalo.edu/courses/cse396/content/hwSol-5.pdf

Thanks very much in advance and please let me know if there is anything I should clarify.

# Answer
Take a larger $i$. The concept is that gaps between $|2^n|$ get bigger than $|y|$.
> 5 votes

# Answer
Let me write down my proof on the question.

We have the language $L = \\{a^{2^n} | n≥0\\}$ and we assume that $L$ is a regular language.

The pumping lemma states that there exists $p \in \mathbb{N}$ such that every string $w\in L$ of length at least $p$ can be written as $w = xyz$, satisfying the following conditions:

1. $|y| ≥ 1$
2. $|xy| ≤ p$
3. $\forall i ≥ 0, xy^iz \in\\! L$

Lets consider the string $w=a^{2^p}, |w|= 2^{p}\geq p$. According to the pumping lemma $w$ can written in the form $xyz$, with $|x|=a^n$, $|y|=a^m$ and $|z|=a^l$. Moreover $xy^iz\\!\in \\! L\\;\forall i\geq 0$. (always remember that $n,l \geq 0$ and $m\>0$)

In other worlds: \begin{equation} n+im+l=2^{p\_i}\\;\\;,\forall\\; i\geq 0\\;(1) \end{equation}

If we plug in $i=0$ at the last equation we obtain a new relation: \begin{equation} n+l=2^{p\_0} \\;(2) \end{equation} Now if we substitute $(2)$ into $(1)$ we get: \begin{align} im &=2^{p\_i}-2^{p\_0}&\\;\\;,\forall\\; i\geq 0\Rightarrow\\ im &= \text{even} &\\;\\;,\forall\\; i\geq 0\Rightarrow\\ m&=2k \end{align},for some $k\in\\! \mathbb{N}$.

The equation $(1)$, now, takes the form: \begin{equation} i\\!\cdot\\!2k=2^{p\_i}-2^{p\_0}\\;\\;,\forall\\; i\geq 0\\;(1.1) \end{equation} If we plug in $i=n+l$ at $(1.1)$ we obtain: \begin{align} 2^{p\_0}\\!\cdot\\!2k&=2^{p\_N}-2^{p\_0}\Rightarrow\\ 2k&=2^{p\_N-p\_0}-1 \end{align} A contradiction. Therefore the initial assumption—that $L$ is a regular language—must be false. (lets note that $p\_n\geq p\_0$ since $\\{p\_i\\}$ is a increasing sequence)
> 1 votes

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


# Question
Title: Why Iterative-Deepening-DFS requires O(b*d) memory?
After reading about iterative deepening depth-first search on Wikipedia, I could understand that it just limits the depth upto which dfs can go in one iteration/call.

However, I could not understand why it is said that it requires $O(b \times d)$ memory, where $b$ is fan-out of nodes i.e. children and $d$ is max-depth.

Since it is just doing DFS multiple times, it should also only need $O(d)$ memory.

Thinking more, I thought that may be the entire graph can not be put in memory and $O(b\times d)$ is the part of graph required to be kept in memory. But does that make DFS also have $O(b\times d)$ memory requirement ? But even this does not like a good argument, because since during traversal if we are fetching the new nodes from some storage, we can do so also with $O(d)$ memory.

Also the Wikipedia page examples lead me to infer that it does not store `visited[node_id]` information about the nodes which stores whether node with id `node_id` is visited till now or not. This made me infer that graph is big.

**Edit:** After thinking further i think that it is right about $O(b \times d)$, since it is iterative-dfs rather than recursive-dfs. In recursive-dfs we usually take memory used by function call stack for granted. In iterative-dfs, we can find right memory-requirements. Since, now we can not implicitly remember back-tracking, we have to put all children on the stack and hence if we are going to $d$ levels, we need $O(b\times d)$ memory.

# Answer
Well, one can say that $O(bd)$ is the bound for iterative-deepening depth-first search (DFID). It is not necessarily true that there is a mistake in Wikipedia. In general, every node is expanded and all its $b$ children are generated. Doing so allows for additional strategies, e.g., sorting them. Then a loop traverses all nodes and DFID is invoked recursively on each one. Thus, when a solution is found at depth $d$, $db$ nodes are stored in memory.

However, in many cases you can do as you suggest and generate the children efficiently one at a time. In this particular case we usually say that DFID takes $O(d)$ (instead of $\Theta(d\log b)$): Instead of expanding all nodes you just take the first one and invoke DFID recursively over it. When the search resumes in this particular node we just take the next one. This sort of implementations works as Tom van der Zanden explained but there is no specific need to remember that we are located at the 2nd child or the 5th child. There are two reasons for this:

1. Once the solution is found, the path to it is in the stack ---so you won't get lost, no need to remember which were the specific orderings of the children generated above your current state.
2. A naive implementation might require remembering we considered the $n$-th child to generate the $(n+1)$-th child but some tricks can be used to avoid this specifically. Take for instance the $N$-puzzle. In this case, the descendants can be precomputed in a table (as Richard Korf did in his original implementation of IDA$^\*$) and the children are just stored in an array of known length. Then $O(d)$ is feasible just by traversing this array. The same trick can be accomplished in other domains such as the $N$-pancake, the Rubik's cube, Topspin (where it is even easier!) and such ...

As a matter of fact, Richard Korf (who originally devised the idea of DFID) describes the space complexity of DFID in page 100 in the following terms: "*since at any given time, it is performing a depth-first search, the space it uses is $O(d)$*" Richard E. Korf. Depth-First Iterative-Deepening: An Optimal Admissible Tree Search. Artificial Intelligence Journal, 27(1). 1985. 99--121 This statement assumes that the considerations made above apply in your domain.

However, it might be a good idea indeed to have a look at all descendants before starting to invoke DFID over them (and therefore incurring in a space complexity $O(bd)$), and Alexander Reinefeld considered a good number of ideas based on this observation. See the paper: Alexander Reinefeld. Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA$^\*$. IJCAI 1993. 248--253.

Finally, a similar idea (ie., generating only a specific node that satisfies a particular condition) has been tried also in the context of A$^\*$. For more information see Meir Goldenberg, Ariel Felner, Nathan Sturtevant, Robert Holte, Jonathan Schaeffer. Optimal-Generation Variants of EPEA$^\*$, Proceedings of the Fifth International Symposium on Combinatorial Search, (SoCS-2013), July 2013

Cheers,
> 1 votes

# Answer
You need $\Theta(d \lg b)$ memory in order to store where in the tree you are: a position at depth $d$ in the tree is given by $d$ integers in the range $1\ldots b$ indicating for each branch in the tree which particular child you're looking at.

You could think of it as a set of directions of how to get from the root node to the current child. For example: at the root, take the 2nd child, then take the 5th child of that node, and so on.

When you're doing DFS, you need this information: once you've considered all children of a node at depth $d$, you need to go back to the previous node at depth $d-1$ and consider its next child, but you can only get to its next child by knowing what child you're currently looking at.

It's not clear why Wikipedia says $O(bd)$. Perhaps this is a mistake in the Wikipedia page.
> 2 votes

---
Tags: graphs, graph-traversal
---


title: Pumping Lemma confusion

text:
# Question
Title: Pumping Lemma confusion
I have the following language...

$$A=\\{a^ib^i | i\>0\\}\cup\\{a^jb^k|j\>2, k\>3\\}$$

Now, pumping lemma states that a regular language can be written in the form $x=pq^ir$. What confuses me is how to split the language into three parts, this is my attempt:

$p=a^j$

$q=a^jb^k$

$r=b^k$

I believe my attempt is incorrect but this is the extent of my knowledge on the subject. Can someone explain how to split the language properly?

# Answer
> 2 votes
The mistake is in what you're attempting to split. The pumping lemma says if $L$ is a regular language, there exists a number $m$ (the pumping length) such that every *string* $x \in L$ can be be split into three parts, $x=pqr$ such that:

1. $|pq| \leq m$
2. $|q| \geq 1$
3. $pq^{i}r \in L$ for all $i \in \mathbb{N}$

So it's the strings in the language that can be split and pumped, not the language.

So for the language you give, which is regular, you should be able to take any string, split it and pump it. One problem with doing this in practice is that the pumping length $m$ is not typically known, however we can take a larger example here and we don't have to worry.

Consider the string $y = a^{2m+3}b^{4}$, then we know that $pq = a^k$ for some $k \in \[1,m\]$, and in particular $p = a^{k\_{1}}$ with $k\_{1} \in \[0,m-1\]$, $q = a^{k\_{2}}$ with $k\_{2} \in \[1,m\]$ and $k\_{1}+k\_{2}=k$. Then $r = a^{2m+3-k}b^{4}$. As $k \leq m$, this string is in the language $A$ (it fits the definition in the second part).

Now we get to the pumping part; as $A$ is regular, assuming that we've split things correctly, we should be able to pump $y$. If we pump down, we get $a^{2m+3-k\_{2}}b^{4}$, which is still in $A$ (again, $k\_{2} \leq k \leq m$). If we pump up $n$ times, we get $a^{2m+3+nk\_{2}}b^{4}$, which still fits the definition and is in $A$.

Then as $A$ is regular, we should be able to do this for every string in the language, but there's no real reason we would want to as it doesn't tell us anything - there are non-regular languages which can still be pumped (e.g. see the wikipedia article). What we use the pumping lemma for is showing that languages *are not* regular by showing that the language we suspect is not regular contains at least one string that cannot be broken up and pumped in any way.

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


# Question
Title: How to efficiently use an AVL tree to store partial sums?
Let $a\_{1} , ... , a\_{m} $ be real numbers $\geq 1$, where $m$ is at least 1. I am supposed to store them in an augmented AVL structure with the following operations:

-PartialSum (i): Return the $i\_{th}$ partial sum.

-Change (i, y): Change the $a\_{i}$ element for y.

I need this structure to retain the AVL properties and both of these functions to be in $O(logn)$. The problem is that my approach doesn't let me have that asymptotic bound on CHANGE.

My approach goes like this: Let i be the key, and also store the relative $i\_{th}$ partial sum in each node, the value for a as well.

Thus each of my nodes has:

1. Key = The $i\_{th}$ element of the series input.
2. Sum = The $i\_{th}$ partial sum so far.
3. Val = The value of $a\_{i}$ for this node.

By doing that, the operation PartialSum will be identical to Search, thus being in $O(logn)$.

Unfortunately my approach doesn't work so well with change. By storing the partial sums in every node, if a lower node changes, all of the tree's sums are to be recomputed, being in $O(n)$.

I am trying to take a different approach but I'm confused. Can someone HINT me here?

# Answer
Instead of storing the whole $i\_{th}$ sum in each node, just store the partial sum of the left sub tree.
> 1 votes

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


# Question
Title: How does this proof show that sequences of $O(1)$ polynomially bounded Kolmogorov complexity are NOT the polynomial computable ones?
I'm trying to understand a proof from the paper: Balcázar, José L.; Gavaldà, Ricard; Hermo, Montserrat: Compressiblity of infinite binary sequences, Published in: *Complexity, Logic, and Recursion Theory*, A. Sorbi, ed., Marcel Dekker 1997, ISBN 0-8247-0026-0, 75-91.

> **Theorem 19** For every recursive time bound f , there is an infinite sequence that is in $C4\[O(1), poly\]$ but not $DTIME(f (n))$-computable. (The sequence is automatically in $C5\[O(1), poly\]$ and in $CK\[O(1), poly\]$.)
>
> **Proof**: The main idea is to build a tally set $T\subseteq\\{0\\}^\*$ with the following properties:
>
> * $\chi^T$ is not $DTIME(f (n))$-computable, where $\chi^T$ is the characteristic sequence of $T$ over $\\{0\\}^\*$
> * $T \in\ DTIME(g(n))$, for some nondecreasing time-constructible time bound $g$ such that $g(n) \gt f (n)$.
> * strings in $T$ are very far one from another; more precisely, $T$ contains only strings of the form $0^{s(m)}$ , where $s$ is defined inductively by: $s(1) = 1;$ $s(m + 1) = g(s(m))$ \[...\]

*(the proof proceeds by using the third property to show that it's easy/polynomial to create $\chi^{T \leq n}$ up to an uncertainty in exactly one hard bit, and so it is possible to consider two machines, one answering $1$ and an other answering $0$ for it, fulfilling the requirement of $\chi^T$ being in $C4\[O(1), poly\]$ )*

This Theorem is claiming to build a tally set that does the job, and I understand how the proof proceeds, once it is taken granted that the set with the specified properties exists, but I don't see its existence proven. How do we know that such a tally set exists for every recursive $f(n)$ that is not $\mathrm{DTIME}(f(n))$ computable as specified in property (1)?

And why do we have to guarantee in property (2) that the $g(n)$ bound is greater or equal to $f(n)$?

Am I missing something basic about tally sets, or sets vs characteristic sequences in general, or some trivial hierarchy theorem?

# Answer
> 3 votes
Wow, that was sooooo long ago. Something like the early nineties...

The point is, for that T, at the time of writing, the construction proper was assumed to be well-established in the background knowledge of any potential reader. Thus, we did not give details. Essentially, what you do is a Cantor-like proof as in the non-numerability of the reals: for each i, run the i-th DTIME(f) machine on a string of s(i) zeros, and add that string to T if and only if the simulated machine rejects it. (Colloquially that string was often called "the cookie".) Then g is to be any time-constructible function that allows for this process to be completed - for this we will need it considerably larger than f. There is a slight circularity in that the process depends on s, which depends on g, which is defined as sufficient time to run the process. But it is easy to upper bound this time and select a sensible g.

Hope this helps! (And hope this works. It is my first time writing anything into stackexchange.)

---
Tags: polynomial-time, kolmogorov-complexity
---


# Question
Title: Algorithm analysis in the presence of undefined functions
I wonder how we can perform algorithm analysis when in an algorithm we have calls of functions whose definition we do not know, e.g. functions delivered by external libraries.

# Answer
> 7 votes
There are two ways to do this. If you're lucky, the implementer of the external library will have given you a runtime analysis of their code. If you're not, you can use an oracle model of computation. In a sense, this is treating the library routines as if they run in constant time. Of course, that would be ridiculous but an oracle-based analysis is a little smarter than that because it allows you to quantify how many times the oracle is accessed. For example, your answer might end up being something like, "The running time is $O(n^2)$ plus the cost of $O(\log n)$ calls to `makeSausage()` on instances of at most linear size."

---
Tags: algorithm-analysis
---


# Question
Title: Is $T=\{\langle M\rangle \mid |L(M)| =1 \text{ or } |L(M)| >2\}$ recognizable?
$$T=\\{\langle M\rangle \mid |L(M)| =1 \text{ or } |L(M)| \>2\\}$$

I started with Rice's theorem (come up with an example where $|L(M)| = 2$) to see that $T$ was undecidable. Then I figured out $\bar{T}$ was unrecognizable, because $H =\\{\langle M \rangle \mid M\text{ halts on the empty string} \\}$ has a mapping-reduction to $T$, and $H$ is not co-recognizable, so $T$ is not co-recognizable.

Now I'm stuck. I tried mapping-reductions from $H$, $E = \\{\langle M \rangle \mid M \text{ doesn't accept anything} \\}$ and $F = \\{ \langle M \rangle \mid L(M) \text{ is finite} \\}$.

What's a good set to try and reduce from (or reduce to)? Am I right that $T$ is unrecognizable?

# Answer
You can establish a reduction $\overline{H}\le\_M T$ by mapping $\langle M\rangle\rightarrow \langle N\rangle$ where

```
N(x) =
   if x = 0, accept
   if M halts on the empty string
      if x = 1, accept

```

Now

* If $\langle M \rangle\in H$ then $L(N) = \\{0, 1\\}$ which implies $\langle N\rangle\notin T$
* If $\langle M \rangle\notin H$ then $L(N) = \\{0\\}$ which implies $\langle N\rangle\in T$

and since you already know $\overline{H}$ is not recognizable, $T$ must not be recognizable.
> 2 votes

---
Tags: computability, turing-machines, semi-decidability
---


# Question
Title: Where does the interrupt handler return to?
Say the CPU is currently handling an interrupt. Another interrupt arrives but it's lower priority than the current one so it gets put in the 'pending interrupt register'. My current interrupt is done so I use a 'return from exception' instruction. Where will this instruction jump to: the address which was interrupted, and then to the interrupt handler or will it immediatly jump to the handler of the new interrupt that is in the 'pending interrupt register'?

# Answer
What happens internally inside the processor could go either way depending on how the designers chose to implement it. Either you are returning to the address that was interrupted, but it immediately gets interrupted again, in which case the next instruction that executes is the first instruction of the next handler, or you are jumping directory to the first instruction of the next handler.

In either case: the first instruction of the next handler will be executed before the instruction that was originally interrupted. Anything else would be a priority inversion bug.
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: Can we write algorithms without conditional statements?
Regarding turing completeness, i read that for a language/machine to be turing complete it is required that it has some sort of conditional.

Consider the factorial problem, we would typically define the algorithm as

**Solution 1.**

```
int fact(int n)
{
if n == 0 then
 return 1;
else
 return n*fact(n-1);
}

```

An alternative would be to define the function fact as

**Solution 2.**

```
int fact(int n)
{
 if n == 0 then return 1;
 elseif n == 1 then return 1;
 elseif n == 2 then return 2;
 elseif n == 3 then return 6;
 ....
 all cases define as above
}

```

Also, another solution would be to have functions like:

**Solution 3.**

```
int fact0()
{
return 1;
}

int fact1()
{
return 1*fact0;
}

int fact2()
{
return 2*fact1;
}

int fact3()
{
return 3*fact2;
}

```

Then we would have an array of function pointers p which we would have to index according to the factorial we want to determine, such that p\[0\] points to fact0, p\[1\] points to fact1, and so forth.

I know that this might sound dumb, but it actually works! What makes solution 1. a valid argument to show that conditionals are required to compute the factorial?

Some additional thoughts on my part:

1. Is solution 1 the only true "algorithm"? Because the other 2 solutions to not seem to "compute" anything
2. Are conditionals required only because we don't know the results (or execution steps) of functions beforehand?

# Answer
> 12 votes
Here is a Turing complete "programming" language. It has just two constants, called $K$ and $S$, and one operation called "application", written $x \cdot y$. The two constants satisfy the rules $$(K \cdot x) \cdot y = x$$ and $$((S \cdot x) \cdot y) \cdot z = (x \cdot z) \cdot (y \cdot z).$$ This is known as a combinatory algebra and is well known to be Turing complete. There is an actual programming language based on $S$ and $K$, called unlambda. I think we can agree that there is no builtin conditional. Of course, since this language is Turing complete, it can also simulate conditional statements.

# Answer
> 2 votes
You'd have to stretch the definition of "conditional" beyond all credibility to say that Turing completeness requires conditionals. Many minimalistic models of computation lack anything remotely resembling a conditional statement, any statement at all, or a conditional *anything*.

For a well-known example, take the untyped lambda calculus. It consists only of defining lambda abstractions and applying them (unconditionally), yet it is Turing complete. Arguable even simpler, the SKI calculus: Which of the following combinators is a conditional?

```
Ix = x
Kxy = x
Sxyz = xz(yz)

```

One problem with your proposals #2 and #3 is that they require (countably) infinite programs to define the function for all inputs. This is generally very undesirable (for starters, this model might decide undecidable problems, or more precisely, have a higher Turing degree).

Oh, of course you're just talking about fewer, more well-behaved and regular programs, where the function for each `n` is generated by a finite mechanical rule. Guess what? Now *that* rule is your program, with or without conditionals. The expansion for various values of `n` is just a trace of the execution for each `n`.

# Answer
> 2 votes
Yes, some sort of conditional is required in a Turing-complete language. It doesn't have to be the if-then-else construct found in most programming languages: there are many other ways to design a conditional. Something in the language needs to capture the essence of the conditional statement, namely, **making the computation path depend on the data**.

If the computation path is independent of the data, then for a given program, the number of computation steps would be predetermined, independently of the input. This is incompatible with Turing-completeness, which allows writing programs that terminate for some inputs and don't terminate for other inputs.

If-then-else is in some sense a minimalist conditional: it takes one bit of data and selects between two execution paths based on the value of this bit.

It's possible to define if-then-else as a macro on top of other primitives. An obvious one is case/switch/match statements, which generalize the idea of selecting execution paths based on some value. It's also possible to define `if` from some more complex primitive that combines a conditional with some other form of flow control, such as a `while` loop.

Note that an `if_then_else` function in a strict language (a language where the arguments of a function are evaluated before the function call) is not a conditional in this sense, because the computation path is always the same (first compute the arguments, then compute the result of the `if_then_else` call). An `if_then_else` function needs to be call-by-need, for its then-value and else-value arguments.

A computed goto statement is another form of conditional. That's what is sketched in your solution 3 is (though your solution 3 isn't a proper definition of a factorial computation, since it would require defining an infinite family of functions). `goto (address1 * condition + address2 * (1 - condition))`, where `condition` can be 0 or 1 standing for true or false, is equivalent to `if condition then goto address1 else goto address2` in a language with a basic if-then-else conditional.

In a Turing machine, conditionals are implemented in a way that's reminiscent of computed goto: at each computation step, the automaton reads a value from the tape and the transition taken by the automaton depends on that value. Each computation step essentially includes a case statement.

In the lambda calculus, conditionals stem from the lack of separation between data and computation — it's all functions. If you want to define a function that makes different computations depending on its argument, just make it apply its argument to something! A basic implementation of if-then-else in the lambda calculus is: $\lambda c. c x y$ — this function takes a “boolean” $c$ and applies it to two arguments. See $\lambda x. \lambda y. x$ as `true` and $\lambda x. \lambda y. y$ as `false` and you recognize $\lambda c. c x y$ as an if-then-else function. (As noted above, this requires an evaluation strategy that isn't pure call-by-value. The lambda calculus with call-by-value reduction is not a Turing-complete model.)

Any Turing-complete set of combinators will have some form of conditional. For example, in SKI, $S$ embeds a conditional, because it applies (computation) its first argument (datum).

# Answer
> 0 votes
**Solution 2** **IS** an algorithm, but it isn't equivalent to **Solution 1**. And this way of writing functions certainly isn't Turing complete.

The only way you can express **Solution 1** in the style of **Solution 2** is making the program infinite, but a Turing machine, by it's very own definition must have a finite set of states.

Of course the style in which you described **Solution 2** can describe *some automata*. I mean, if you go on with the idea of having a table that maps input into functions – I can't prove it formally now – I'm pretty sure it will lead to something equivalent to a **deterministic finite automaton**, which can describe some languages/problems, but is far from a Turing machine.

---
Tags: turing-machines, programming-languages, turing-completeness
---


# Question
Title: Solution verification: solving $T(n) = T(n-1) + 2/n$
I was wondering if someone could possibly verify my solution to the following:

I'm trying to solve the recurrence relation $T(n) = T(n-1) + 2/n$. To get it into the form of the Master Theorem, I note that for sufficiently large $n$, $n - 1 \geq n/2$. Moreover, $2/n = O(1)$. Thus, we can rewrite the equation as $T(n) = T(n/2) + O(1)$. Since $\log\_21 = 0$, it then follows directly from the Master Theorem that $T(n) = O(\log(n))$.

-Thanks!

# Answer
Although the final result is correct, your solution is not.

The recurrences of the form $T(n) = T(n-1) + 2/n$ is often called "decrease and conquer"; while the ones of the form $T(n) = T(n/2) + O(1)$ is called "divide and conquer". Generally, they are different and cannot be reduced to each other.

**Hint:** To solve $T(n) = T(n-1) + 2/n$, you can expand it and notice that $1 + 1/2 + \cdots + 1/n = H(n) = \Theta(\lg n)$, the $n$-th partial sum of the harmonic series (wiki).
> 4 votes

# Answer
No, this solution is unfortunately false. You remark that for sufficiently large $n$, $n-1 \geq n/2$ (indeed, $n \geq 2$ would do). The recurrence easily implies that $T$ is increasing, so $n-1 \geq n/2$ implies that $T(n-1) \geq T(n/2)$. All you can deduce is that $T(n) \geq T(n/2) + 2/n$, which cannot imply any upper bound on $T(n)$. Even the lower bound you get is only $\Omega(1)$.

If you forget about the Master Theorem, then you can notice that $$ \begin{align\*} T(n) &= T(n-1) + \frac{2}{n} \\ &= T(n-2) + \frac{2}{n-1} + \frac{2}{n} \\ &= \cdots \\ &= T(0) + \frac{2}{1} + \cdots + \frac{2}{n} \\ &= T(0) + 2H\_n, \end{align\*} $$ where $H\_n = \sum\_{k=1}^n (1/k)$ is the $n$th Harmonic number. It is well-known that $H\_n = \log n + \Theta(1)$ (indeed, the complete asymptotic series is known), and so $T(n) = 2\log n + \Theta(1)$.
> 2 votes

---
Tags: algorithms, recurrence-relation
---