Difference between Sequential ,Direct and Random acess with their acess time I'm stuck on a point while reading about these different accessing methods. As per author.

Sequential access

  Memory is organized into units of data, called records.Access must be made in a specific linear sequence.

I understand that it will take variable time to access due to sequential ordering.

Direct Access

  individual blocks or records have a unique address based on physical location.Access is accomplished by direct access to reach a general vicinity plus sequential searching,counting,or waiting to reach the final location. Again, access time is variable.

Here I'm Stuck that if we have unique address why it is taking variable time and why we can't directly access data.

Random Access

  Each addressable location in memory has a unique,physically wired-in addressing mechanism. The time to access a given location is independent of the sequence of prior accesses and is constant.

What is the difference between this and direct access method.

Sometimes, depending on the sources,direct access and random access are used to express the same memory access mode and therefore do not present any substantial difference in the speed of data access.

More in detail, the differences between the two modes can be sought in their implementation:
Random Access can be realized directly via RAM memory wiring, while direct access can use secondary storage; in this case is obvious that random access is faster than direct access.


Is decimal number 8 represented as 3 bits or 4 bits in computer? I was told by my professor that

"It takes c * ln(n) bits to store a number n, where ln() is base 2 and c is a constant."

Thus, to store a number 8, we need ln(8) = 3 bits(I think const c can be ignored here.), but isn't 8 stored as "1000" in a computer, which is 4 bits?

Thanks.

$b$ bits have a total of $2^b$  distinct bit-patterns. To store 8 distinct values, you need at least 3 bits.

This does not tell you on its own how many bits are required to store the number 8, because it depends on the way that you assign numbers to bit patterns.

A typical "unsigned integer" uses $b$ bits to represent the numbers 0, 1, ... 2^b-1. In that format, you would need 4 bits to represent 8, because $2^3-1<8<2^4-1$.

A typical "two's complement integer" uses $b$ bits to represent the numbers $-2^{b-1}$ to $2^{b-1}-1$. In this format, you would need 5 bits to represent 8, since $2^{4-1}-1<8<2^{5-1}-1$.

If you're only interested in representing powers of two (perhaps because you doing something hardware or memory related, where divisions such as alignment are only ever powers of two), you use fewer bits; for example, if 00 is 1, 01 is 2, 10 is 4, and 11 is 8, you only need 2 bits to represent 8.


Data Compression :Compress a Compressed File Suppose we have file A that has been compressed by the the method B and the output-file is C, now if I am not wrong We can not compress C more by method B, but there might another method=algorithm D that  might compress C more and produce compressed file E.

Is this kind method of using more than one compression-method in each iteration of compression   standard? if there is a paper/survey paper on performance of such kind of compression,  please, comment or post an answer.

I mean, is there any study where 2 or 3 methods were apply to same file,   if there is a paper/survey paper on performance of such kind of compression, please, comment or post an answer.

The essential problem is that most files are NOT compressible (see the counting argument). And an already compressed file is much less likely to be compressible.


Insert into binary tree and keep it balanced Assuming each node stores its depth, how can I achieve this? Note that I'm not talking about a binary search tree so I shouldn't need rotations. All I want is filling the tree from left to right.

You can keep all leaves in a queue, and on insertion set the new node as a child for the q.front(), add the new node to the queue and check if the numbers of children of the node in front of the queue = 2 then pop the node out of the queue.
To remove a node you can swap the node you are removing and the last added node delete the last one (you should remove it from the back of the queue as well).

However, I would implement it as an array where a[0] is the root of the tree and a[i*2 + 1], a[i*2 + 2] are the children of a[i]. Inserting would be in this case to add an element to the back of the array and to remove an element you can swap it with the back of the array and pop the back of the arrray


M is a Determinstic TM with one tape, c2 is c1 reachable, if it's reachable within finite positive time $M=(Q,\sum,\Gamma, \delta, q_{0}, q_{accept}, q_{reject})$ is a TM with one tape.
let $c_{1}, c_{2}$ be two configurations of $M$.

A configuration is defined like this:

$uqv$  where $(q\in Q; u,v\in \Gamma^{*} )$

we say that $c_{1}$ is reachable from $c_{2}$ in $M$, if when $M$ is in configuration $c_{1}$ it can reach the configuration $c_{2}$ in a finite number of steps that is greater than 0.

Is the following language TR (Turing Recognizable), is it Decidable?

$L=\{\langle M, c \rangle  \mid M\text{ is a TM; configuration }c\text{ is reachable from configuration }c\text{ in }M\}$?

I know that the answer to this is no, $L$ is not Decidable. I just fail to see the logic behind that.

See I thought $L$ is Decidable because of the following justification:

$L$ is decided by the structure of $M$ it's self with no regards to whatever language $M$ accepts so it is intuitive.

Let's run $M$ non diterministically on any letter of it's alphabet until we get to cofiguration $d\ne c$ then again to reach another config. and so on until we get to configuration $c$ it's self after a threshold number of steps, let's say $N^{q}$ number of steps, where $N$ is the number of configurations in $M$ and $q$ is the number of letters in alphabet.

Kindly explain why language $L$ is TR and not Decidable.

Thank you in advance.

Since no answer has been posted I will attempt the answer my self:
Since Giacomo explained why $L$ is TR(I thank him for that) I won't talk about it.

I will prove $L$ is not decidable:

We do that by building a machine $K$ that will decide the halting problem $L_{1}$ using $G$ the decider of $L$ that we assume exists.

$L_{1}$={< $R$, $w$ > | $R$ is a TM; $w \in \Sigma^{*} $; $R$ halts on $w$ }

Description of $K$:

Build TR $H$ that has a configuration $c$ as follows:

"Configuration $c$": On input <$R$, $w$ > if $R$ halts on $w$ go to configuration $d$ which on any input goes back to configuration $c$.
else go to configuration $e$ and loop forever.

Run $G$ on input <$H$,$c$ > if $G$ accepts, accept else reject.(if $H$ accepts $K$ accepts and vice-versa)

Giving < $R$,$w$> to $K$ as input, $K$ will decide if $R$ halts on $w$  if and only if (iff) $G$ decides if $c$ is reachable from $c$ in $H$.

But we know that the halting problem is not decidable in contradiction to what we have assumed in the first place, so $G$ cannot exist there for $L$ is not decidable.


Context Free Grammar for {a^ib^j | i,j ≥ 0; i ≠ 2j} Can someone help with this:

$L=\{a^ib^j \mid i,j \ge 0 \text{ and } i \ne 2j\}$

I'm trying to write a grammar for this language?
I don't know how to do this.
I tried this:
$S \rightarrow aaAb \mid aA \\
A \rightarrow aA \mid a$

Consider the two languages:
$L_1 = \{a^ib^j \mid i, j \ge 0 \text{ and } i > 2j\}$
$L_2 = \{a^ib^j \mid i, j \ge 0 \text{ and } i < 2j\}$

Convince yourself that $L = L_1 \cup L_2$.

In $L_1$, the number of $a$'s are more than double of $b$'s, so there has to be atleast one $a$ (when there are no $b$'s). Also, for every addition of $b$, atleast 2 $a$'s must be added. You can generate $L_1$ as:

$
S_1 \rightarrow aA \\
A \rightarrow aaAb \mid aA \mid \varepsilon
$

$L_2$ is a little more tricky. The number of $a$'s are less than double the number of $b$'s, so there can be $0$ $a$'s, but non-zero $b$'s. Consider the "base case" of $1$ $b$. The string can be either $b$ or $ab$. We will let the first rule generate this base case. After that, notice that for every addition of $b$, we can increase the number of $a$'s by at most $2$. So we can add $0$, $1$, or $2$ $a$'s for every addition of $b$. We'll let the second rule handle this. So, the CFG for $L_2$ becomes:

$
S_2 \rightarrow Bb \mid aBb \\
B \rightarrow Bb \mid aBb \mid aaBb \mid \varepsilon
$

Note that CFG's are closed under union, that is, the union of two CFG's is also a CFG. So, to get the CFG for $L$, let the starting state $S$ of $L$ lead to either the starting state of $L_1$, or of $L_2$:

$S \rightarrow S_1 \mid S_2$

The rest of the rules remain the same as in the two languages. There may be a simpler grammar, but this was the first that came to mind.


What is meant by 'simultaneously computing' all partial derivatives of an arithmetic circuit? I was reading the proof that for every arithmetic circuit of size $s$ and depth $d$ we can find a circuit $D$ of size $\mathcal{O}(s)$ and depth $\mathcal{O}(d)$. I do not understand what is meant when we say that we can construct a circuit which 'simultaneously computes' all partial derivatives of a function. Does simultaneously computing mean that there are multiple output gates or does it mean that every partial derivative is computed by some sub-circuit of of $D$.

The new circuit will have multiple output gates, each one computing a different partial derivative. See for example Definition 2.1 and the ensuing proof in lecture notes of Wigderson.


Reducing Graph Reachability to SAT (CNF) So I came across this problem in my textbook. I was wondering how to develop a reduction from the Graph Reachability problem to SAT (CNF) problem. (i.e. formula is satisfiable iff there exists a path in graph G from start to end node)

1) I can't wrap my head around how to go from something that can be solved in polynomial time (Graph Reachability) to something that is NP (SAT).

2) I can't seem to find a way to formulate these nodes/edges of Graph into actual clauses in CNF that correspond to reachability.

I tried to think about algorithms like Floyd-Warshall that determine if a path exists from start to end node but I can't seem to formulate that idea into actual CNF clauses. Help would be much appreciated!

Maybe the solution is to use the 2-SAT problem which does have a polynomial solution.

For a 2-SAT problem, you can indeed build an implication graph. Basically a clause $(a \vee b)$ leads to the implications $\neg a \implies b$ and $\neg b \implies a$. The problem is satisfiable if there is no variable $x$ such that $x$ and $\neg x$ are in the same SCC of the implication graph. Being in same SCC is equivalent to double reachability:

it exists a path from $x$ to $\neg x$
it exists a path from $\neg x$ to $x$

So for any skew-symmetric (required property) graph, you can build a 2-SAT problem for which it is the implication graph.


How much more powerful are regexes in modern programming languages compared to regular expressions from the theory of computation? Are the ones in modern programming languages equivalent to, say, Context-Free Grammars or is there an intermediate (between finite automata and CFGs) set of languages that it covers?

A famous example: a PCRE that finds primes. I couldn’t find Abigail’s original, but there have been many iterations on this.

In JavaScript, for example, you can pass a function to the matcher to do arbitrary computation with the results.


Lambda calculus didn't seem abstract. And I can't see the point of it The underlying question:

What does lambda calculus do for us that we can't do with the basic function properties and notation generally learned in middle school algebra?

First of all, what does abstract mean in the context of lambda calculus? My understanding of the word abstract is something that is divorced from the machinery, the conceptual summary of a concept.

However, lambda functions, by doing away with function names, prevents a certain level of abstraction. For example:

f(x) = x + 2
h(x, y) = x + 5 y

But even without defining the machinery of these functions, we can easily talk about their composition. For example:

1. h(x, y) . f(x) . f(x) . h(x, y) or
2. h . f . f . h

We can include the arguments if we want, or we can abstract away completely to give an overview of what's happening. And we can quickly reduce them to a single function. Let's look at composition 2. I can have student layers of detail I can write with depending on my emphasis:

g = h . f . f . h
g(x, y) = h(x, y) . f(x) . f(x) . h(x, y)
g(x, y) = h . f . f . h = x + 10 y + 4

Let's perform the above with lambda calculus, or at least define the functions. I'm not sure this is right, but I believe the first and second expressions increment by 2.

(λuv.u(u(uv)))(λwyx.y(wyx))x

And to multiply by 5y.

(λz.y(5z))

Rather than be abstract, this seems to get into the very machinery of what it means to add, multiply, etc. Abstraction, in my mind, means higher level rather than lower level.

Furthermore, I am struggling to see why lambda calculus is even a thing. What is the advantage of

(λuv.u(u(uv)))(λwyx.y(wyx))x

over

h(x) = x + 5 y

or a combined notation

Hxy.x+5y

or even Haskell's notation

h x y = x + 5 * y

Again, what does lambda calculus do for us that we can't do with the f(x)-style function properties and notation many are familiar with.

There are many reasons why the lambda calculus is so important.

A very important reason is the lambda calculus allows us to have a model of computation in which computable functions are first-class citizens.

One cannot express higher-order functions in the language of middle school algebra.

Take as example the lambda expression

$$\lambda f. \lambda g. \lambda x. f(g(x))$$

This simple expression shows us that, within the lambda calculus, function composition is itself a function. In middle school algebra, this is not easily expressed.

In the lambda calculus, it is very easy to express that a function will return a function as its result.

Here is a small example. The expression (where I here assume an applied lambda calculus with addition and integer constants)

$$(\lambda f. \lambda g. \lambda x. f((g(x)))(\lambda x. x+2)$$

will reduce to

$$\lambda g. \lambda x. g(x)+2$$

Notice also that within the lambda calculus, functions are expressions and not definitions of the form $f(x) = e$. This frees us from the need to name functions and to distinguish between a syntactic category of expressions and a syntactic category of definitions.

Also, when it becomes impossible (or just notationally cumbersome) to express higher-order functions, one will also have problems with assigning types to expressions.

Function composition has the polymorphic type

$$\forall \alpha.\forall \beta. \forall \gamma. (\beta \rightarrow \gamma) \rightarrow ((\alpha \rightarrow \beta) \rightarrow \gamma)$$

in the Hindley-Milner type system.

A very strong selling point for the lambda calculus is precise the notion of typed lambda calculus. The various type systems for functional programming languages such as Haskell and the ML family are based on type systems for lambda calculi, and these type systems provide strong guarantees in the form of mathematical theorems:

If a program $e$ is well-typed and $e$ reduces to the residual $e'$, then $e'$ will also be well-typed.

And if $e$ is well-typed, then $e$ will not exhibit certain errors.

The proofs as programs correspondence is particularly noteworthy. The Curry-Howard isomorphism (see e.g. https://www.rocq.inria.fr/semdoc/Presentations/20150217_PierreMariePedrot.pdf) shows that there is a very precise correspondence between the simply typed lambda calculus and intuitionistic propositional logic: To every type $T$ corresponds a logical formula $\phi_T$. A proof of $\phi_T$ corresponds to a lambda term with type $T$, and a beta-reduction of this term corresponds to performing a cut elimination in the proof.

I urge those who feel that middle school algebra is a good alternative to the lambda calculus to develop an account of higher-order, polymorphically typed middle school algebra together with an appropriate notion of Curry-Howard isomorphism. If you can even work out an interactive proof assistant based on middle school algebra that would allow us to prove the many theorems that have been formalized using lambda calculus-based proof assistants such as Coq and Isabelle, that would be even better. I would then start using middle school algebra, and so, I am sure, would many others with me.


Polynomial-time algorithm to solve the maximum vertex bipartite subgraph problem I'm trying to find an algorithm that solves the maximum vertex biclique problem. I know that that algorithm can be solved in polynomial time (in contrast with the maximum edge biclique problem, which is NP-hard), and it's related somehow to transform the problem to a network flow problem, but I'm having a hard time finding it because most of the results from google are about NP-hard problems with similar wordings like maximum edge biclique problem, maximum vertex coverage and such.
Could anyone provide a link, explanation or even a pseudocode algorithm about how to solve the maximum vertex biclique problem in polynomial time?

The problem is equivalent to the Maximum Independent Set problem on the "bipartite complement graph" (take the complement graph and delete edges with both endpoints on the same side of the bipartition). Such an MIS is the complement of a Minimum Vertex Cover, which can itself be deduced from a Maximum Matching.
You can probably take it from here (with maybe a bit of googling for how to find a Minimum Vertex Cover in a bipartite graph).


Context free languages belongs to NTIME(n)? As the question states, how do we prove that for every L ∈ L2 (context-free class of languages) is true that L ∈ NTIME(n)?

Can anyone point me to a proof or outline it here? Thanks!

Hint: Every context-free language is accepted by a pushdown automaton.


How to classify simple priority queue algorithm I have a simple priority queue algorithm that I implemented, and I doubt it's new
but I haven't been able to classify it. Wondering if I could get some help with classifying it! Once I classify it I can read more about how to implement it properly, etc.

Assuming the implementation is sound, I am also trying to figure out how to prove certain aspects of the queue, namely to determine if the maximum amount of time (or steps) for an item to come off the queue is deterministic.
Ideally we could figure out how long that would be as a function of some variables and initial state, or what not.

Here is the basic algorithm:

Setup/background/assumptions:

We have a FIFO queue, and each item in the queue has a priority of 1, 2, or 3 (generically, we could make it 1 -X  where those are all integers). By FIFO we mean that, in general, items that are enqueued first get dequeued first, but with a priority queue that is not exactly the case (that should be pretty obvious).
3 is highest priority, 1 is lowest priority, the higher the number the higher the priority.
Let's assume a single server for simplicity, but the concept should be similar enough for multiple servers.
Assume we only take one item off the queue at a time, but this same algo should work if we pop off multiple items.

Algorithm:

(Note that the only question at hand is: What item do we pop off the queue next? That is what the algorithm is trying to solve).

Step 1: For all your priority levels, determine a number of cycles for each level. Higher priority levels should have more cycles - so let's say priority 3 has 10 cycles, priority 2 has 6 cycles and priority 1 has 2 cycles.

Step 2: Instead of looking at the whole queue, look at only the first Y items, for example the first 20 items. This makes things faster (O(20) instead of O(n)), and easier to prove that the implementation is working as expected. Most importantly, setting this cap should prevent starvation for the lower priority levels. Because eventually the 20 items will be filled with lower priority items, and then they will start seeing some attention.

Step 3: Every time you dequeue an item, increment an integer. Then mod this integer against the total number of cycles (10 + 6 + 2) = 18. This will determine which priority cycle you are in, for any given dequeue event.

Step 4:
Take the value from the mod operation, determine what cycle you are in by comparing the value to an accumulated cycle value, e.g.:

Priority     Cycles      Accumulated

3            10           10

2            6            16

1            2            18

In that way if the mod result of our incremented integer is in the range
0 - 10 we are in priority 3 mode, if the mod result is in the range 11-16 we are in priority 2 land and if the mod result is in the range 17-18 we are in priority 1 realm.

Step 5: Sort the first 20 items in the head of the queue, first by priority level, then by age, oldest to the front.
Given the priority level found from step 4, look through the sorted list find the first one that is at the priority level or below. So if we are at priority 3 we will look at all items. If we are at priority 2, we look at items with priority 2 and below, etc etc.

Step 6: If no items can be found with priorty Z and below, then cycle to the highest priority again, in this case 3, which will always yield something off the queue.

Done.

The basic idea is that our priority system is is based off of the number of cycles given to each priority, where more cycles are given to higher priority items. This should make things more deterministic.

But like I said, I am most interested in (a) proving this actually works somehow and (b) determining some value for maximum time (or steps) for an item to come off the queue.

You can't prove an algorithm is correct without a specification what correctness means.

This algorithm isn't a priority queue.  A priority queue has two properties: pop always removes the highest-priority item; and it resolves ties (in priority) in a FIFO fashion.  Your algorithm doesn't do that; if the first 20 items in the last are all low priority, but there's a high-priority item elsewhere, a priority queue would return the high-priority item, but your algorithm returns a low-priority item.

A true priority queue is easy to implement if you only have three priority levels: you just have three ordinary queues, one for each priority level.  When pushing an item, push it onto the corresponding queue.  When popping an item, first look at the level-3 queue and pop off of it if it is non-empty; otherwise check the level-2 queue and pop from it if it is non-empty; otherwise pop from the level-1 queue if the other two queues are empty.  This achieves $O(1)$ time for all priority queue operations.

Possibly you are looking for information on process schedulers; this is studied in the operating systems area.


Average case complexity of search data structures Algorithms are generally studied in terms of average case complexity and worst case complexity? Is there also a kind of analysis called "average worst case" complexity?

One such notion is that of smoothed analysis, in which we compute the worst-case expected complexity of an algorithm on a randomly perturbed input. In more detail, let $N(x)$ be a randomly perturbed version of $x$, and let $T$ be the time complexity of the algorithm. Then we are interested in
$$
\sup_x \mathbb E[T(N(x))].
$$
The "worst case" aspect is with respect to the unperturbed input, and the "average case" aspect is with respect to the perturbation.

The simplex algorithm has been shown to be polynomial time in this sense, although its worst case complexity is exponential.


Number of conflict serializable schedules Two transactions $T_1$ and $T_2$ are given as:
$$T_1: r_1(X)w_1(X)r_1(Y)w_1(Y)$$
$$T_2: r_2(Y)w_2(Y)r_2(Z)w_2(Z)$$
where $r_i(V)$ denotes a read operation by transaction $T_i$ on a variable $V$ and $w_i(V)$ denotes a write operation by transaction $T_i$ on a variable $V$. The total number of conflict serializable schedules that can be formed by $T_1$ and  $T_2$ is _______________

I have tried finding the total number of schedules – nonconflict serializable schedules, but I think there is a higher possibility in committing mistakes in the exam for that method. Please suggest a better way to solve this.

While checking for conflict serializable schedules, we should be sure to avoid RW, WW, WR conflicts. Also the relative order of operations internal to each transaction also needs to be maintained. For example T1's operations on $X$should come before T1's operations on $Y$. Also since $Y$ is the common datum here, therefore either all of T1's operation on $Y$ occur before T2's $Y$ operations or they may occur later, but they shouldn't be interleaved.

So let's try to see the number of such serializable schedules:
Here is $T_1$:

  (a)  $r_1(X)$ (b) $w_1(X)$   (c) $r_1(Y)$  (d)  $w_1(Y)$  (e)

Since $Y$ is the common datum so I pick it first from $T_2$.
put $w_2(Y)$ at position (a)

  (a1) $w_2(Y)$ (a2) $r_1(X)$ (b) $w_1(X)$   (c) $r_1(Y)$  (d)  $w_1(Y)$  (e)

We now have two new positions (a1) and (a2). Now, see that $r_2(Y)$ can come only at (a1) since it cannot come after $w_2(Y)$. Now The $Z$ operations of $T_2$ remain. See that they can come at any of the 5 postions starting from (a2) till (e). So for this case, we get total schedules as

$1 *( \binom{5}{1} + \binom{5}{2}) = 15$

$\binom{5}{1}$ is the case when both $r_2(Z)$ and $w_2(Z)$ come together. $\binom{5}{2}$ is the case when they are separated. Note that $r_2(Z)$ and $w_2(Z)$ have not been permuted to maintain their relative order.
Similarly, you can move $w_2(Y)$ through positions (b) (c) and (e)  (note that (d) is an excluded possibility since interleaving is not allowed) to get $20, 18, 1$ as the answer respectively for each individual case. They sum up to $54$.

In case you need the explanation for all cases, you can look up here.


TM - reject definition and complement I have couple of questions about Turing machines:

What is the definition of the "reject" state in TM?
If the input was very small and, after one step, the machine gets to the end of the input, but it stands on regular state, it counts as "reject"? Or there is a special "reject" state, and if it won't get to this/those states, it doesn't count as a reject? (I know that in DFA, the reject states are just all the states that aren't "accept".)
I know that in aDFA, if we swap the reject and the accept states, we get the complement language. Does this work on TMs?
If I use only the TM's input cell (including changing their content), does it means I used $\mathrm{SPACE}(1)$ or $\mathrm{SPACE}(n)$?

Thanks a lot!

There's a special reject state. Unlike a DFA, which is terminated by the definition when it reaches the end of the input, the machine decides when it stops, by jumping to one of the halting states (depending on exactly what definition you're using, there might be just one "halt" state, or there might be separate "accept" and "reject" states).
Almost. If the Turing machine accepts or rejects every input, then swapping accept and reject does indeed compute the complement, since you reject every string that you would have accepted, and vice-versa. However, we can also define languages in a weaker way, where the Turing machine accepts all strings in the language but, for a string not in the language, it might reject or it might just get stuck in an infinite loop (this is called "accepting", "recognizing" or "semi-deciding" a language).  In this case, just swapping the accept and reject states doesn't complement the language, since the inputs that loop forever don't reach either state, so you'd conclude that such a string is neither in the language nor it's complement, which can't possibly be right.
No. Normally, when defining space classes, we use a slightly different model.  When considering space-bounded computations, we Turing machines with three tapes: a read-only input tape, a write-only output tape and a read/write working tape. In this model, we only count the space used on the working tape. Because the input tape is read-only, you're not allowed to write to its input, unless you first copy the input to the working tape, in which case you're using space $n$.


In an NFA, what if there are no transitions out of an accept state but there are symbols left in the string? Let's say I have a string 0110 and after 011 I reach an accept state (let's call the accept state "q") in an NFA. However, there is no transition mentioned in the diagram from q for the symbol 0. Does this mean the computation dies, or does this mean that the string is accepted?

Finite automatas (either) DFA or NFA, must be process the entire input string.
DFAs will keep track of a single state while processing a string. Think of it as a pointer to the current state. It will transition (i.e. move that pointer) according to its rules while processing a string. Remember that for a DFA, all states must have a transition for each symbol in the alphabet. Thus, the DFA will have a unique path to the final state after processing the entire input string. If final state is an accepting state after processing the entire input string, the string is accepted; otherwise, it is rejected.
NFAs on the other hand will keep track of a set of states while processing a string. Think of it as having a set of pointers to all possible states for which the NFA could have transitioned to after processing a certain number of symbols. This allows for the NFA to not have all transitions defined, the inclusion of $\epsilon$ on transitions, and having a symbol on more than one transition out of a state. If the set of states contains an accepting state after processing the entire input string, the string is accepted; otherwise, it is rejected.
Take the following example:
$L = \{0,1\}^*00^+1 + \{0,1\}^*01^+0$. The following NFA accepts this language.

We can make a chart that shows how the NFA will process an input string. The left column indicates the current set of states (when we start processing we start with {A}). The middle column is the set of states possible from the current set of states after processing a 0, and similarly for the right column with 1.
              0         1
_________ | ________ | _______
{A}       | {A,B,C}    {A}
{A,B,C}   | {A,B,C,D}  {A,C,D}
{A,B,C,D} | {A,B,C,D}  {A,C,D}
{A,C,D}   | {A,B,C,D}  {A,C}
{A,C}     | {A,B,C,D}  {A,C}

Suppose we have an input string 001. The NFA will process the input:
0 from {A}       -> {A,B,C}
0 from {A,B,C}   -> {A,B,C,D}
1 from {A,B,C,D} -> {A,C,D}

We see that the final set of states is {A,B,C,D} which does contain an accepting state. Thus, $001 \in L$. Notices while processing the string, the NFA did not record the way it got to the accepting state; it just records that it is possible to get to one.
Suppose however we have an input string of 0011. The NFA will process the input:
0 from {A}       -> {A,B,C}
0 from {A,B,C}   -> {A,B,C,D}
1 from {A,B,C,D} -> {A,C,D}
1 from {A,C,D}   -> {A,C}

We see then that the final set of states is {A,C} which does not contain an accepteing state. Thus, $0011 \notin L$.

TL;DR
FAs must process the entire input. For NFAs, if the final set of possible state the machine could end in contains a final state, then the input string is accepted; otherwise, it is rejected.


Quantum computing roadmap I have to create a roadmap for the quantum computing technology. Looking around I found the timeline on wikipedia that is pretty wide but does not highlight the key events in quantum computing research neither sets the possible future for research.

Could somebody help me to define which are key events in the quantum computing fields? When (and why) we started to explore this technology, for which milestones we passed through and (maybe) what we can set as future milestones?

This Quantum Information Science and Technology Roadmapping Project is a very detailed roadmap prepared under ARDA (Advanced Research and Development Activity) around ~2004 with further refinements. Here is the introduction/overview. It had a panel of about 19 elite academic scientists/experts.

For a completely contrasting recent overview/review on progress to date/future prospects see this [controversial] paper State of the Art and Prospects for Quantum Computing, M. I. Dyakonov (2012).


About the first order logic (valid, Unsatisfiable, Syntactically wrong) I am in trouble , I searched a lot about how to solve this kind of questions but I did not get any answers.

I understand how can I know when the sentences is valid and Unsatisfiable in propositional logic, but in FOL I can't.

Can someone help me how can I solve this kind of questions? Because it comes always in the past exams in AI.

Let us have the following:

1- ¬(Speed(Processor(MyPC))=Speed(Processor(MyPC)))
2- ¬ ∃ x ( Speed(x) = Speed(MyPC) )
3- Speed(MyPC)=MyPC
4- ∀ y ∃ x (Speed(x) ∧ Speed(y))= Speed(MyPC)

Note :

    MyPC:
    a constant symbols that represents my PC.

    Speed(x):
    a function symbol that refers to speed of x

The answer for 1 is Syntactically wrong
2 is Unsatisfiable
3 is Neither valid nor unsatisfiable
4 is Syntactically wrong

1 uses a function symbol Processor which is not in the logic signature. Hence, it's outside the syntax.

4 tries to equate a proposition with Speed(MyPC). You can't equate propositions in FOL. Outside the syntax.

3 is not universally true for every function Speed and every argument MyPC.
For instance interpret MyPC as the natural $0$, and Speed as the successor function to obtain $\mathsf{succ}(0)=0$ which is false. Hence the formula is not valid. However, it is satisfiable: now interpret MyPC as zero and Speed as the identity function to obtain $\mathsf{id}(0)=0$ which is true. The formula has a model and a countermodel: satisfiable and invalid.

2 ∃ x ( Speed(x) = Speed(MyPC) ) is always true, since we can take x to be MyPC. This holds no matter how we interpret Speed and MyPC. Hence is it valid. (Alternatively, we can even show it is a theorem of FOL using a proof system, and then rely on the correctness theorem to claim it is valid.) Since formula 2 is the negation of a valid formula, it is unsatisfiable.


How can Computer Science theories and inquiries be resolved? It's probably possible to prove that P ≠ NP, that one-way functions exist, and that parity games cannot be solved in polynomial time (yes, I've been reading through this list), but how would we go about proving any of those things? Have there been any proofs to any computer science theories, or answers to any substantial computer science questions (such as the ones in that list)? Are they like mathematical proofs (such as Grigori Perelman's resolution to the Poincaré conjecture)? I know that the P versus NP problem seems out of my league, being a junior in high school, but it's a problem that intrigues me, and I would really like to see how others (if any) have answered other, related questions, because I would like to look into a resolution to the problem.

This isn't a duplicate of this question primarily because physics isn't computer science, and secondarily because, unless I'm mistaken, computer science theories are not proven the same way that theories related to physical sciences are proven. They're more like mathematical proofs in that they're logical (right?).

Theoretical computer science, to which the questions you state belong, is part of mathematics, and the methods used to resolve questions are the same ones used elsewhere in math, namely the method of proofs. The questions you list are notoriously difficult, and seem to be out of reach for current methods.

In the past, the methods used to attack questions of the sort you describe were purely combinatorial. Recently, Ketan Mulmuley and his students have come up with a different method which employs representation theory (via some algebraic geometry), and is conjectured by them to be one day strong enough to resolve the P versus NP question. Currently, though, the only questions within reach of their methods are algebraic ones like permanent versus determinant rather than Boolean ones like P versus NP.

Since it is widely (though not universally) believed that P is different from NP, many results are proved conditional on this assumption. That is, they hold only if P is indeed different from NP. The area of hardness of approximation, which studies how well different combinatorial problems can be approximated in the worst case (in polynomial time), is a good example: all results in this area are conditional on P versus NP or on some even stronger assumptions.


Grammatical characterization of deterministic context-free languages Deterministic context-free languages are commonly defined using an automaton concept, the (restricted, deterministic) pushdown automaton. To some that is confusing, as the name context-free refers to a grammar type.

I seem to remember there exists a characterization of the DCF languages using grammars. In my recollection it used a complicated equivalence on non-terminals. Can anyone provide a pointer to that work?

Wikipedia actually gives you the model and points to [1] for reference: LR grammars are equivalent to DPDA.

On the Translation of Languages from Left to Right by Donald Knuth (1965) [free download]


Textbooks about non-RE languages for undergraduate students I'd like to read up on non-recursively enumerable languages. Which textbooks should I look into to get a decent understanding about the subject?
Thank you.

Despite its name, Soare's book Recursively enumerable sets and degrees has lots of information about this. In particular, it covers in pretty good detail the arithmetical hierarchy.
(Incidentally, note that the non-r.e. elements of the arithmetical hierarchy aren't all "r.e.-hard." For example, consider any minimal $\Delta^0_2$ degree, that is any Turing degree $\le_T{\bf 0'}$ which is nonzero but not strictly above any nonzero Turing degree. There are infinitely many minimal $\Delta^0_2$ degrees; by the Sacks Density Theorem, they are all non-r.e. and hence by minimality don't compute any nonrecursive r.e. sets. The way in which the r.e. degrees sit inside the $\Delta^0_2$ degrees is actually fairly complicated.)


Why is abstraction in lambda calculus called abstraction? The term abstraction as I understand it, is used in many different contexts, but has one essential meaning, namely that it refers to the “general properties of some class of objects that doesn’t rely on their details”. For example, abstraction in programming is e.g. interfaces that allow you to constrain a set of objects without specifying certain implementation details.

But in lambda calculus, I don’t see what “function abstraction” has to do with something like “independence of details”. It seems to me like “function application” or “argument substitution” makes more sense.

Am I missing something?

Ps. Note that I have only read an introductory chapter of a book on lambda calculus.

Abstraction in the context of lambda calculi means turning some part of a term into a variable. Let's do an example. Consider the following terms (which use a notation richer than pure lambda calculus):

$1 + 2$
$\sin^2(\varphi) + \cos^2(\varphi)$
$\frac1{n + 1}t^{n + 1} + C$

They have one thing in common. They all are built from smaller terms using $+$. Now, if we want to abstract away from the details and focus on the general common property of these terms, we just turn everything that is not $+$ into variables and end up with $\lambda x.\lambda y.x + y$, a function abstraction (if that is the name your introductory text uses; I am more familiar with the name "lambda abstraction").


DFA that accepts any integer $n$ such that $n \bmod 7 =1$ It seems impossible for me to find a pattern for integers $n$ such that $$n \equiv 1 \quad(\bmod 7)$$ in order to construct this DFA.

Is there smart way to do it without a machine which has memory or completes operations? A hint would be greatly appreciated.

I assume you are talking about integers encoded in some base $b \geq 2$, and we're reading the integer from left to right.

An inductive hint: say we have read the number $n$ so far, and our inductive assumption is that we are in state $n \bmod 7$ (so we have 7 states). We read the digit $d$. Our next state should be $bn + d \bmod 7$. How do we correctly determine what state to go to, since we don't know $n$?

Well the trick is that while you don't know $n$, you do know $n \bmod 7$. And:

$$bn + d \equiv b(n \bmod 7) + d\mod 7$$

So for example, in base $10$, if we are in the state $3$ (meaning $n \equiv 3 \mod 7$) and we just read the digit $8$, our next state will be  $10\cdot 3 + 8 \equiv 3 \mod 7$. In other words, state $3$ points to itself on reading digit $8$ in base $10$.


Stable marriage problem with more people then priorizations I am trying to solve a stable marriage problem where I have e.g. 20 women and 20 men, but they always only prioritise 4 pre-selected people of the opposite sex.

My algorithm distributes all men and women, so that everybody has 4 potential partners. This happens through the whole group of 20 (not in groups of 4 x 4, which would easily work). If man A has woman B in his list then he is also in her list.
The people prioritise their potential partners from 1 to 4.
My algorithm tries to find the optimal partner depending on their priorization.

This means that they marriage has to be with one of the 4 potential partners. The order of their prioritisation decides on the order the proposing and accepting matrix is gone through, similar to this animation shown in wikpedia.

So basically I have 20 rows of each proposers and acceptors, but only 4 columns.

So far I always get an almost stable solution, in which in the end only one man and one woman can not marry.

How could I solve this problem for even bigger numbers of people (rows), but always keeping 4 (or between 3 and 5) prioritisation (columns)?

In general, you won't be able to marry all but one of the men and all but one of the women. For example, suppose that all of the men want to marry the same four women: you'll get exactly four marriages and an arbitrarily large number of bachelors and spinsters.


How do you apply a multi qubit gate to specific qubits in a multi qubit circuit? Let's say that you have a 6 qubit system and you want to apply a Hadamard gate to qubits 2 and 4.

How would you construct a matrix that did that, while leaving the state of the other qubits alone?

Imagine that the qubits were $0$ and $1$ (or $1$ and $2$, depending on your numbering scheme). You want to apply the Hadamard gate on the first two coordinates, and nothing – the identity – on the rest. This leads to a block diagonal matrix whose second block is the $4\times 4$ identity.

Now make the necessary arrangements for the qubits you're interesting it.


What is the difference between 'features' and 'descriptors' in computer vision / machine learning? I've read multiple time sentences similar to

  Finally, for standard image classification bag-of-words
  features based on SIFT descriptors have been found
  critical for high performances. We first compute a
  standard SIFT discriptor at regular grid points over
  the whole image.

Source: "Multi-class image segmentation using Conditional Random Fields
and Global Classification" by Nils Plath, Marc Toussaint, Shinichi Nakajima.

What is a descriptor? I thought  SIFT is an algorithm which operates on images and gives features (vectors in $\mathbb{R}^n$, where $n$ is fixed for a fixed size of images and parameters of the SIFT algorithm)?

The SIFT descriptor vector is a feature vector.  "Descriptor vector" and "feature vector" are synonyms in this context.  Most of the descriptions of SIFT I've seen use the phrase "descriptor vector", but occasionally they'll refer to it as a "feature vector" or refer it to as "SIFT features", perhaps to draw upon intuition from machine learning.

SIFT works by analyzing the image, identifying a set of keypoints (a set of points in the image that will be helpful for alignment), and then for each keypoint, it computes a descriptor vector (a feature vector).  Then it uses the descriptor vectors for the keypoints in image $I_1$ and the descriptor vectors for the keypoints in image $I_2$ to try to align the two images to each other.  The intuition is that if the descriptor vector for a keypoint in image $I_1$ is "similar" to a descriptor vector for a keypoint in image $I_2$, then maybe those two points should be aligned to each other.  Here "similarity" is measured by the Euclidean distance between the two descriptor vectors.

Thus, a descriptor vector for a keypoint is a vector, e.g., in $\mathbb{R}^{128}$, chosen so that if the image is translated, scaled, rotated, etc., then the descriptor vector for that point won't be changed much by the transformation.

You can find a reasonable description of SIFT in Wikipedia: https://en.wikipedia.org/wiki/Scale-invariant_feature_transform


Context Free or Context Sensitive and why I was given two languages

$$L_1=\{0^k1^k0^m\mid k,m \in \mathbb{N}\text{ and }k < m\}$$

and

$$L_2=\{a^mb^{m+1}\}$$

and I was asked to prove whether they are context free or sensitive.

For $L_1$ : I did pumping lemma and I cannot clearly rule out the context free. So I accepted that it is and tried to do a high level description of a pda. I check the first part of the language $0^k1^k$ like this: push A for every 0 you read pop A when you read 1. If the stack is not empty reject. But I have trouble finding how to check the second part, $1^m$ with $m>k$. So now I do not know if it is indeed a context free.

For $L_2$ I followed a similar method with $L_1$ and again I stuck in the $m+1$ part.

Can someone help me? I am not proficient in grammar creation and pdas and lbas were only taught in our class in high level descriptions like the above.

Hint 1: You can write the languages as $0^k1^k0^k0^{m-k}$ and $a^mb^mb$.

Hint 2: If a language looks non-context-free, but the pumping lemma does not show this, you can try Ogden's lemma.


Build all valid parenthesis in polynomial time Given some binary operator $\otimes : X\times X\to X,$ and list $x_1,\dots,x_n$ where $x_i\in X,$ can all possible expressions in $\otimes$ be computed within a number of operator applications polynomial in $n$?

We say an expression in an operator $\otimes$ and list $x_i$ is formed by placing $\otimes$ between all $x_i$ in order with some choice of parentheses. For example given the list $x,y,z,$ valid expressions are $(x\otimes y)\otimes z$ and $x\otimes (y\otimes z)$. Alternatively, an expression in $x$ is precisely $x$ and an expression in $x_1,\dots,x_n$ is an expression in $x_1,\dots,x_{k-1},x_k\otimes x_{k+1},x_{k+2},\dots,x_n$ for some $1\le k < n.$

We assume that there are no more than polynomially bounded amount of setting the parenthesis (because its given in the assignment) and thus it has to run in polynomial time.

I'm doubting my solution so far, here it goes:

We define two working sets

$ result = \{ \}$

$ vars = \{\}$

Every single input variable is a valid expressions if it is paired with another valid expression ( since our operand is two-valued), and we add them to the vars set.

Now iterate through lengths $ 2, \_,n$ and build all valid expressions like so:

For length $2$ we build all valid strings like so: $w_1 = (x_0 \circ x_1) , w_2 =(x_1 \circ x_2) \ldots $ and add them to the $vars$ set.

For length $>3$ we greedily iterate through the biggest available chunks in the $vars$ set and try to fill up the voids with items from our vars set until we reach length 3.

Once we reach length $n$ we add all generated expressions to the $res$ set and return.

One thing I'm stuck on right now is the complexity analysis, one iteration of the subexpression generation takes $n^2$ steps at most, when we reach length $n$ we get $n^3$ complexity (much like CYK, which is very similar to this algorithm).

But something feels fishy, I feel like I've made a mistake somewhere, can someone point me in the right direction ?

This is an assignment so full answers are discouraged, please give hints, once I get the grading of the answer I'll post it here for the afterworld to admire.

"We assume that there are no more than polynomially bounded amount of setting the parenthesis"

Your assumption is wrong.  There are exponentially many such expressions.  In particular, each such expression corresponds to a full binary tree with $n$ leaves (i.e., a binary tree where each non-leaf node has exactly 2 children).  There are exponentially many such trees.  Consequently, there are exponentially many such expressions.

It follows that you can't generate the list of all such expressions in polynomial time, since it takes exponential time even just to write down the answer (let alone to find it in the first place).


thread scheduling in multi core architecture In multi core architecture, let us say we have M cores and N threads (N > M) and a process once assigned to a core can't migrate to another core's ready queue. We have to design scheduling policy to balance load.
I read about this area and found this -
1) Block multithreading, Interleaved multithreading and Simultaneous multithreading (https://en.wikipedia.org/wiki/Multithreading_(computer_architecture))
2) Round Robin, FIFO, preemptive scheduling
(https://en.wikipedia.org/wiki/Scheduling_(computing))
3) Threads inherit priority number from processes and go to relevant core
My question asks me to compute thread load before scheduling and then assign that thread to core which is less loaded. Is there any research work done in this area ? If not, is there any research work done which computes a thread's computational load at compile time ?

The load balancing or multiprocessor scheduling problem is one of the earliest NP-hard problems for which an approximation algorithm has been developed.  The classic paper is:

  R.L. Graham: "Bounds for certain multiprocessing anomalies," Bell System Technical Journal, 45(9):1563–158, 1966.

In the load balancing problem you are given $M$ identical cores, and $N$ threads.  All the threads are assumed to be available at the beginning, and all the thread run times are given before hand.  Graham proved that list scheduling, taking the threads one-by-one and assigning each one to the machine that currently has the least load is a 2-approximation.  He further proved that Longest processing time (or LPT) scheduling, where you sort the threads in decreasing order of running length before doing list scheduling is a 4/3-approximation algorithm.  See, for example: https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/11ApproximationAlgorithms-2x2.pdf

Graham's original result has been extended over the years to cases where there are dependences between jobs (i.e., job $j$ needs to finish before job $k$ starts), and to where each job $i$ is not permitted to be scheduled before a given time $a_i$ (known as the arrival time), and to where the machines have different properties, and the jobs have requirements about what machine properties are required.

In the case where the job lengths and/or arrival times are not known before hand the problem becomes much harder.  This becomes an online algorithm.  The main research I am aware of in this area is for the case where the jobs do have dependences between them, but the dependences are restricted to fork-join patterns.  The work in this area started (afaik) with the paper

  Robert D. Blumofe; Charles E. Leiserson: Scheduling multithreaded computations by work stealing. J. ACM 46(5):720-748, 1999.

(Note that this is called "work stealing", but you should really view the work being stolen as a new, dependent, job, so it actually fits into the non-migratory requirement you specified.)

As to your other question: there has been some work in using type inference to infer program running times, but I don't know that anything practical ever came out of it.  The paper I'm aware of is:

  Brian Reistad; David K. Gifford: Static Dependent Costs for Estimating Program Execution Time, ACM Conf on Lisp and Functional Programming, 1994.


Regular grammar with at most one c I am attempting to make a regular grammar over alphabet {a, b, c} where there is at most one c. So far, I have the regular expression ((a|b)*|c)(a|b)* but am unsure where to go from here; my previous attempts have ended up allowing multiple c's.

The solution I has gives (N={s,t}, T={a,b,c}, s, R), s→є, s→as, s→bs, s→ct, t→at, t→bt, t→є, however I do not see how this limits the number of c's generated to at most 1.

The rule s->ct can only be done once, becuase after that there is no more s left, and from t you cannot generate more s. Thus at most one c can be generated, because no other rule generates c.

Also the rest of the grammar looks fine.


Kernel Perceptron vs Polynomial Perceptron I was looking at Support Vector machines (SVM) kernels. Looking at Polynomial Kernel and Kernel Perceptron I was curious how they differ?

Work Done

Polynomial Kernel:

$d_{k+1}(x)=d_{k}(\bar{x})+\rho k(\bar{x}_{k}, \bar{x})\; \mbox{if}\; \bar{x}_k\epsilon\,C_1$

$d_{k+1}(x)=d_{k}(\bar{x})-\rho k(\bar{x}_{k}, \bar{x})\; \mbox{if}\; \bar{x}_k\epsilon\,C_2$

where $k(\bar{x}_{k}, \bar{x}) = (\bar{x}\cdot \bar{x}_{k}+1)^{q}$

Kernel Perceptron:

This is given by

$g(x)=\sum_{j=1}^{N}a_{j} K(\bar{x},\bar{x}_j)$

So as per my understanding a bias constant is added in former case when compared to later. So how does that impact and what difference does it make? Or am I missing something?

Any insights are appreciated.

A SVM with a polynomial kernel is a SVM classifier.

A kernel perceptron is a perceptron classifier, or in other words, a neural net.

A SVM is quite different from a neural net.  So, that's one way that they differ.

However, Wikipedia says that SVMs are in some respects a generalization of a kernel perceptron, generalized with regularization.  Regularization is basically a form of Occam's razor: it says that, all else being equal, simpler models are preferred over more complex models.  Regularization helps avoid overfitting and thus is very useful in practice.

(Related: See also Support Vector Machines as Neural Nets? -- a SVM with a linear kernel is similar to a single-layer perceptron classifier, in case that's what you were thinking of.)


Algorithm to organize a tournament where the team componentes change each round So, I was tasked with creating an app that generates the schedule of a doubles tennis tournament (i.e., teams of two) in a way that, by the end of it, everyone would have played against the rest of the players. The trick is every team should change in each round so that not only everyone played against everyone but the teams are not repeated.

I've tried implementing it using greedy search with backtracking, but it just takes too long to find a valid solution, so what I'm asking for is sugerences of an algorithm more efficient that I can use to solve this problem. This are the especifics of the problem:

There is a multiple of 4 number 'n' of players.
There is at least n/4 fields to play, so that in each round all players have a match.
No player can play twice with the same partner, so in each round the teams must change.
No player can play twice against the same opponent. At the end of the tournament, each player must have played against the rest.

The algorithm must search the ideal combination of matchs so it meets the requeriments above.

Any ideas? Thank you in advance.

EDIT 2: It's not possible for 4 players.

ROUND 1

Player 1 & Player 2 vs Player 3 & Player 4

So far so good.

ROUND 2

Player 1 & Player 3 vs Player 2 & Player 4

Player 1 already played against Player 4, not a valid solution. The other possibility:

ROUND 2'

Player 1 & Player 4 vs Player 2 & Player 3

Player 1 already played against Player 3, not a valid solution either.

EDIT: It is double tennis, sorry for the misunderstanding.
Each player must have played against the rest, but it's not mandatory that each player ended up playing with the rest.
Question edited for clarity.

Sorry, but there is no solution. (Assuming that all games are 2 vs 2.)

How many matches does each player play?

They play with each other player exactly once, one such player per match, for a total of $n-1$ matches.
They play against each other player exactly once, two such players per match, for a total of $\frac{n-1}{2}$ matches.

This implies $n-1=\frac{n-1}{2}$ and thus $n=1$. But you said $n$ is even. And besides, a single-player tournament would not be interesting.

[EDIT]

The question was now changed to omit the requirement that every other player is a partner at least once. However, it is still not possible.

How many rounds should there be? For every player there are $n-1$ potential opponents. In every round there are $2$ opponents without repetition. Hence the number of rounds is $\frac{n-1}2$. This is not an integer number, because $n$ is even.


What is Least-Constraining-Value? In constraint satisfaction problems, heuristics can be used to improve the performance of a bactracking solver. Three commonly given heuristics for simple backtracking solvers are:

Minimum-remaining-values (how many values are still valid for this variable)
Degree heuristic (how many other variables are affected by this variable)
Least-constraining-value (what value will leave the most other values for other variables)

The first two are pretty obvious and simple to implement. First choose the variable that has the least values left in its domain, and if there are ties, choose the one that affects the most other variables. This way if a parent step in the solver picked a bad assignment, you are likely to find out sooner and thereby save time if you choose the variable with the least values left that affects the most other things.

Those are simple, clearly defined, and easy to implement.

Least-constraining-value is not clearly defined, anywhere I looked. Artificial Intelligence: A Modern Approach (Russel & Norvig) just says:

  It prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph.

Searching for "least-constraining-value" only turned up a lot of university slide shows based on this textbook, with no further information on how this would be done algorithmically.

The only example given for this heuristic is a case where one choice of value eliminates all choices for a neighboring variable, and the other does not. The problem with this example is that it this is a trivial case, which would be eliminated immediately when the potential assignment is checked for consistency with the problem's constraints. So in all the examples I could find, the least-constraining-value heuristic didn't actually benefit the solver performance in any way, except for a small negative effect from adding a redundant check.

The only other thing I can think of would be to test the possible assignments of the neighboring variables for each assignment, and count the number of possible assignments of the neighbors that exist for each possible assignment of this variable, then order the values for this variable based on the number of neighbor assignments available if that value is chosen. However, I don't see how this would offer an improvement over a random order, since this requires both testing numerous variable combinations and sorting based on the results from counting.

Can anyone give a more useful description of least-constraining-value, and explain how that version of least-constraining-value would actually yield an improvement?

see this link:

https://people.cs.pitt.edu/~wiebe/courses/CS2710/lectures/constraintSat.example.txt

It first picks variable "O" and then tests "O" with all of it's legal values "i" to see the number of reductions on "O"'s neighbors "N". It adds all of them. and picks an "i" that causes less reductions:

   sums = {0:0,1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
   For i from 0 to 9:
     plug "o=i" into the constraint formulas
     For each neighbor "N" of "o" in the constraint graph:
       sums[i] += the number of values remaining for "N"

It picks "i" so that:

sums[i] = MAX{sums[i] | for all "i" that is a member of "O",s valid values}

I hope This can help you find your answer!


Determining most efficient algorithm for a problem This is a very straightforward question, and I apologize if it is a repeat. All I want to know is if there is any general method for determining how efficient the most efficient algorithm for some problem is, in terms of time. Barring that, are there any specific methods used that have accomplished the same for a particular problem? If this is not possible in general or at all what are the hurdles to this, and is there any research along these lines?

Note that there is a problem with no maximally efficient algorithm.

The problem "Is it the case that x has an even number of 1s and

the Turing machine M halts within length(x) steps?" is such that

$\:$ if M halts then the problem takes linear time to solve, since for inputs whose length exceeds

$\:$ the amount of time it takes for M to halt, the algorithm will have to look at each bit of x
 $\;\;\;\;$ and
$\:$ if M does not halt then the problem can be solved

$\:$ in constant time, since the answer is no for all x

.
Therefore, deciding how efficient the most efficient algorithm for some problem is, to the

extent that makes sense, is at least as hard as the halting problem. $\:$ On the other hand,

you may be interested in the circuit minimization problem and/or DFA minimization.


On efficiency analysis of randomized divide-and-conquer median find I read following explanation from Dasgupta's Algorithms book for Median finding, this is the same philosophy applied in randomized quick-sort.
Here as per book terminology $S$ denotes array of integers, $v$ is pivot, $S_{L}$ and $S_{R}$ are left and right side of pivot element.
To distinguish between lucky and unlucky choices of $v$, we will call $v$ good if it lies within the 25th to 75th percentile of the array that it is chosen from. We like these choices of $v$ because they ensure that the sub lists $S_{L}$ and $S_{R}$ have size at most three-fourths that of $S$ (do you see why?), so that the array shrinks substantially. Fortunately, good $v$’s are abundant:
half the elements of any list must fall between the 25th to 75th percentile!
In one of the interview it was asked to me up till what range this median finding gives average running time of $n$.
i.e. Favourable range of selection is within 25 to 75 percentile. But up to what extent we can reduce this and still have average running time of $n$
My approach was to write recurrence relation and then from the height of the tree comment on average running time, but I doubt is it a correct way to have answer? Also it might not provide tighter bounds.
It will be helpful if someone can also suggest what mathematical tool/technique will be useful for this kind of analysis.

There's no need to do any calculation. There is absolutely nothing special about the numbers 25 and 75.
If $0 < \alpha < \beta < 1$ and you are promised that the median is between the $\alpha$'th percentile and the $\beta$'th percentile, then the running time of the algorithm will be linear. Indeed, if $\gamma = \min(\alpha,1-\beta)$, the length reduces by a factor of at least $1-\gamma$ in each recursive call, so the total running time will be proportional to at most
$$ n \sum_{i=0}^\infty (1-\gamma)^i. $$
Even without computing the sum, we can tell that in converges, so we get a bound of $O(n)$. If we compute the sum, we get the dependence on $\gamma$:
$$ \frac{n}{\gamma}. $$
This sort of behavior always occurs when we reduce a problem to a subproblem which is smaller by a constant factor bounded away from 1. Once you know that, you don't need to do any calculations.


Turing Machine that always returns a blank tape Is it possible to construct a Turing Machine such that given any finite input on a tape $s$, it clears the tape in a finite amount of time?

I have used such a TM as an intermediate step to show a reduction from the State Entry Problem to is $w \in L(M)$ problem but I don't know if it is feasible to construct one.

Even if we assume that the head of the TM always starts at the leftmost character on the tape and keep moving write, clearing each symbol we encounter, if the tape is infinite, how will we know when to stop moving right?

While the tape is infinite, the amount of characters written on it is finite at any given point in time.

As sasha indicates in their comment, we usually assume that the tape is initialized with a special blank character. Given a Turing machine, you can modify it so that whenever it visit a cell having the special blank character, it replaces it with some other blank character, which it treats the same as the special blank character. Now at any given point in time you can find the (finite) extent of tape which has been visited, and clear it if you wish.


Definition and properties of support From Xiong, Hui, Shashi Shekhar, Pang-Ning Tan, and Vipin Kumar. “TAPER: A Two-Step Approach for All-Strong-Pairs Correlation Query in Large Databases.” Knowledge and Data Engineering, IEEE Transactions on 18, no. 4 (2006): 493–508.
:

  Support measures the fraction of transactions that contain a
  particular subset of items. The notions of support and correlation may
  not necessarily agree with each other. This is because item pairs with
  high support may be poorly correlated while those that are highly
  correlated may have very low support. For instance,
  suppose we have an item pair {A, B}, where supp(A)
  = supp(B) = 0.8 and supp(A, B) = 0.64. Both items are uncorrelated because supp(A, B) = supp(A)supp(B). In contrast, an item pair {A, B}
  with supp(A) = supp(B) = supp(A, B) = 0.001 is perfectly correlated
  despite its low support.

I don't quite follow the example about support. Could anyone give a proof of $supp(A)supp(B) = supp(A, B) \iff A \text{ and } B \text{ are uncorrelated}$ ? I don't even quite understand what $supp(A, B)$ means. Is there a book or paper on support vs correlation?

First, the definition is clear: support is exactly "the fraction of transactions that contain a particular subset of items." This is a data-mining term, not a statistics term.

$supp(A)$ is the fraction of transactions that contain item $A$. $supp(B)$ is the fraction of transactions that contain item $B$. $supp(A,B)$ is the fraction of transactions that contain the subset $\{A,B\}$.

Now, your question really seems to be more about how the authors expound on this, which does seem to be a little unclear. As a statistic, support can basically mean, "What is the probability that this subset of items is contained in a random transaction?" That is, you can consider that $supp(A)=\mathbf{P}(A)$.

Then you can see that
$$supp(A)supp(B) = supp(A, B) \iff A \text{ and } B \text{ are uncorrelated}$$
comes from the definition of statistical independence,
$$\mathbf{P}(A\cap B) = \mathbf{P}(A)\mathbf{P}(B) \iff A \perp B.$$


Don't understand this graph definition I'm studying for my finals in algorithms and reading the part about flow networks. There's a certain section that has me completely stumped and it is as follows:

  Given a graph $G= \langle V_G, E_G \rangle$, we can construct the $H(G)=\langle V_H, E_H\rangle$ as follows:
  $$V_H = V_G\times\{0,1\}$$
  $$E_H = \{((v,0),(v,1))|v\in V_G\}\cup\{((x,1),(y,0))|(x,y)\in E_G\}.$$
  Say that we have a graph $\langle G,u,v\rangle$ where $G$ is some directed graph, which contains vertices $u$ and $v$ then $H(G)$ can be used to find the smallest number of nodes that must be removed from $G$ to separate $u$ to $v$, meaning there will be no simple path from $u$ to $v$.

I really don't understand what's going on here, partly because I can't visualise $H(G)$. I assume we'd get some bipartite graph and maybe apply Edmonds-Karp only because the flow networks sections is succinct and there's not much else in this chapter. Could someone tell/show me what $H(G)$ is doing exactly and why this result is true. Much appreciated.

EDIT:

I've added some images of the what I got for $H(G)$ for some simple graphs. I understand that the function will transform a graph into a bipartite graph. But, how does this graph tell us the minimum number of vertices that have to be removed so there doesn't exists a simple path from $u$ to $v$ in the original graph? I'm perhaps wondering if it is a maximum matching problem in disguise.

D.W.'s advice to consider some small examples is excellent.  Two great examples to start with are an isolated vertex and a single edge!  Once you can how the construction transforms vertices and edges, you know what happens to the building blocks.

Also, some familiarity with the basics of these constructions helps.  In particular, any time you see "Let the vertex set of the new graph be $V\times S\,$" for some set $S$, you should think: "Take a copy of $V$ for every element of $S$, and label each copy with the element it's associated with."  So, here, the vertex set of $H$ is two copies of $G$'s vertex set: one labelled $0$ and one labelled $1$.  Now, look at the edges.  The first set of edges says, "For every vertex $v\in G$, add an edge from copy $0$ to copy $1$." The second set says, "For every edge $(x,y)\in G$, add an edge from copy $1$ of $x$ to copy $0$ of $y$."


Write a regular expression - Contains an equal number of 01 and 10 subtrings I'm trying to write a regular expression for the language $L\subseteq\{0,1\}^*$ of strings that begin with $0$ and contain an equal number of occurrences of the substrings $01$ and $10$. Substrings can overlap, so $010$ is in the language but, e.g., $01101$ is not.

I've worked on a DFA where I can move on to create the RE. Here is my DFA:

I'm trying to use Arden's theorem to get the regular expression but I'm  stuck. This is how I'm thinking:

\begin{align*}
a_1 &= 0a_2 + e\\
a_2 &= 0a_3 + 1a_5\\
a_3 &= 0a_3 + 1a_4\\
a_4 &= 0a_3 + 1a_4\\
a_5 &= 0a_6 + 1a_5\\
a_6 &= 0a_6 + 1a_5\,.
\end{align*}
I dont describe $a_7$, the "sink state" because it only results in the empty set.

My problem here is that I will never be able to get describe the language because of how $a_3$, $a_4$ ,$a_5$, $a_6$ are? Where did I go wrong?

After some work, I came to this solution, is it correct?

$$0 + 00(11^*0 + 0)^* + 01(1 + 00^*1)^*00^*$$

Part of your confusion stems from the fact that there are two different formulations of Arden's Lemma, which I'll call LR and RL. To illustrate them, let's take a simple FA with three states, $P,Q,R$, where $P$ is the start state and $R$ is the only final state. The transitions are
$$\begin{array}{c|cc}
 & 0 & 1\\ \hline
P & Q & \varnothing\\
Q & R & Q\\
R & R & R
\end{array}$$
It's clear with a moment's thought that the language accepted by this FA is denoted by the regular expression $01^*0(0+1)^*$, so let's see what the two versions of Arden's Lemma produce.

LR: In this version we generate the regular expression from left to right. If we have a state $X$ with a transition on $a$ to state $Y$ we will include the equation $X=aY$, along with any other terms that arise from transitions from $X$ to other states. Along with this, we add a "$+\epsilon$" to the expression for $X$ if $X$ happens to be a final state. Having made the collection of equations, we may apply the simplification rule that says that whenever we have $X=rX + s$ for regular expressions $r, s$ we can replace the equation by its solution $X=r^*s$. Note that here the goal is to product a regular expression for the start state.

In the example above, we'll have the equations
$$\begin{align}
P&=0Q\\
Q&=0R+1Q\\
R&=(0+1)R+\epsilon & \text{since R is final}
\end{align}$$
Substituting, we see that $R=(0+1)^*\epsilon = (0+1)*$ and $Q=1^*(0R)=1^*0(0+1)^*$, and finally $P=0Q=01^*0(0+1)^*$, as we expected.

RL: In this version we construct the regular expression from right to left. The difference is that if we have a state $X$ with transition on $a$ to state $Y$ we include the equation $Y=Xa$, along with any similar terms. In this case, we add the "$+\epsilon$" only to the start state's equation and the substitution in this case says that if we have $X=Xr+s$ we have the solution $X=sr^*$.

Returning to our example, we'll have
$$\begin{align}
P&=\epsilon & \text{since $P$ is the start state and has no incoming transitions}\\
Q&=P0+Q1\\
R&=Q0+R(0+1)
\end{align}$$
Now our goal is just opposite of what we had in the LR version: we want an expression for the final state, $R$. Working from the top down we have $Q=Q1+P0=Q1+0$ so $Q=01^*$ and $R=Q0(0+1)^*=01^*0(0+1)^*$: the same result generated in a different order.

Assuming you want to use the LR version, your equations should be
$$\begin{align}
a_1&=0a_2\\
a_2&=0a_3+1a_5+\epsilon\\
a_3&=0a_3+1a_4+\epsilon\\
a_4&=0a_3+1a_4\\
a_5&=0a_6+1a_5\\
a_6&=0a_6+1a_5+\epsilon
\end{align}$$
As for your problem with $a_5, a_6$, for example, we could do this:
$$\begin{align}
a_5 &= 1^*(0a_6)=1^*0a_6 & \text{Arden}\\
a_6 &= 0^*(1a_5+\epsilon) &\text{Arden again, now substitute $a_6$}\\
a_5 &= 1^*0[0^*(1a_5+\epsilon)]\\
    &= (1^*00^*1)a_5+1^*00^* &\text{so we have}\\
a_5 &= (1^*00^*1)^*1^*00^*
\end{align}$$


search problem vs optimization problem This is mostly a terminological question: Is there a fundamental difference between "optimization problems" and "search problems"? Apologies if this is an obvious question
As I understand it, we can define the two as follows (note, I consider the problem for a fixed input size for brevity):

Search problem. Given a set $X$ of candidate solutions, and a property $P:X\to \{\text{True}, \text{False}\}$, find an $x\in X$ such that $P(x)$.
Optimization problem. Given a set $X$ of candidate solutions, and a criterion function $F:X\to \mathbb R$, find an $x\in X$ such that $x\in \arg\max_{y\in X} F(y)$.

But it seems to me that to say that a search problem $P_S$ is "reducible" to an optimization problem $P_O$ is an understatement: They seem to be exactly the same apart from a "stylistic" difference:

Given a search problem $P_S=(X,P)$, define optimization problem $P_O=(X,F)$ where $F(x) = \begin{cases}1 \quad \text {if }  P(x)\\0\quad \text {if } \neg P(x) \end{cases}$
Given a optimization problem $P_O=(X,F)$, define search problem $P_S=(X,P)$, with $P(x)=  \begin{cases}\text{True} \quad \text { if }  x \in \arg\max_{y\in X} F(y)\\\text{False}\quad \text { if } x \notin \arg\max_{y\in X} F(y)\end{cases}$

Is there really not a fundamental difference between these two problems? Or are they fundamentally different in some way that I'm overlooking?

The fundamental difference in these two problems lies in the verification of a proposed solution.

The solution of a search problem is only as hard to verify correct as the predicate itself.

The solution of an optimization problem needs special arguments or proofs to avoid having to search the entire domain to verify a solution correct, which often may not exist or are not known.

This means that simply finding a solution is enough for a search problem, but without a proof or exhaustive search an instance for an optimization problem is uncertain.


Why, really, is the Halting Problem so important? I don't understand why the Halting Problem is so often used to dismiss the possibility of determining whether a program halts. The Wikipedia article correctly explains that a deterministic machine with finite memory will either halt or repeat a previous state. You can use the algorithm which detects whether a linked list loops to implement the Halting Function with space complexity of O(1).
It seems to me that the Halting Problem proof is nothing more than a so-called "paradox," a self-referencing contradiction in the same way as the Liar's paradox. The only conclusion it makes is that the Halting Function is susceptible to such malformed questions.
So, excluding paradoxical programs, the Halting Function is decidable. So why do we hold it as evidence of the contrary?
4 years later: When I wrote this, I had just watched this video (update: the video has been taken down). A programmer gets some programs, must determine which ones terminate, and the video goes on to explain that it's impossible. I was frustrated, because I knew that given some arbitrary programs, there was some possibility the protagonist could prove whether they terminated. I knew many real-life algorithms had already been formally proven to terminate. The concept of generality was lost somehow. It's the difference between saying "some programs cannot be proven to terminate," and, "no program can be proven to terminate." The failure to make this distinction, by every single reference I found online, was how I came to the title for this question. For this reason, I really appreciate the answer that redefines the halting function as ternary instead of boolean.

Because a lot of really practical problems are the halting problem in disguise. A solution to them solves the halting problem.

You want a compiler that finds the fastest possible machine code for a given program? Actually the halting problem.

You have JavaScript, with some variables at a high security levels, and some at a low security level. You want to make sure that an attacker can't get at the high security information. This is also just the halting problem.

You have a parser for your programming language. You change it, but you want to make sure it still parses all the programs it used to. Actually the halting problem.

You have an anti-virus program, and you want to see if it ever executes a malicious instruction. Actually just the halting problem.

As for the wikipedia example, yes, you could model a modern computer as a finite-state machine. But there's two problems with this.

Every computer would be a different automaton, depending on the exact number of bits of RAM. So this isn't useful for examining a particular piece of code, since the automaton is dependent on the machine on which it can run.
You'd need $2^n$ states if you have n bits of RAM. So for your modern 8GB computer, that's $2^{32000000000}$. This is a number so big that wolfram alpha doesn't even know how to interpret it. When I do $2^{10^9}$ it says that it has $300000000$ decimal digits. This is clearly much to large to store in a normal computer.

The Halting problem lets us reason about the relative difficulty of algorithms. It lets us know that, there are some algorithms that don't exist, that sometimes, all we can do is guess at a problem, and never know if we've solved it.

If we didn't have the halting problem, we would still be searching for Hilbert's magical algorithm which inputs theorems and outputs whether they're true or not. Now we know we can stop looking, and we can put our efforts into finding heuristics and second-best methods for solving these problems.

UPDATE: Just to address a couple of issues raised in the comments.

@Tyler Fleming Cloutier: The "nonsensical" problem arises in the proof that the halting problem is undecidable, but what's at the core of undecidability is really having an infinite search space. You're searching for an object with a given property, and if one doesn't exist, there's no way to know when you're done.

The difficulty of a problem can be related to the number of quantifiers it has. Trying to show that there exists ($\exists$) an object with an arbitrary property, you have to search until you find one. If none exists, there's no way (in general) to know this. Proving that all objects ($\forall$) have a property is hard, but you can search for an object without the property to disprove it. The more alternations there are between forall and exists, the harder a problem is.

For more on this, see the Arithmetic Hierarchy. Anything above $\Sigma^0_0=\Pi^0_0$ is undecidable, though level 1 is semi-decidable.

It's also possible to show that there are undecidable problems without using a nonsensical paradox like the Halting problem or Liars paradox. A Turing Machine can be encoded using a string of bits, i.e. an integer. But a problem can be encoded as a language, i.e. a subset of the integers. It's known that there is no bijection between the set of integers and the set of all subsets of the integers. So there must be some problems (languages) which don't have an associated Turing machine (algorithm).

@Brent: yes, this admits that this is decidable for modern computers. But it's decidable for a specific machine. If you add a USB drive with disk space, or the ability to store on a network, or anything else, then the machine has changed and the result doesn't still hold.

It also has to be said that there are going to be many times where the algorithm says "this code will halt" because it the code will fail and run out of memory, and that adding a single extra bit of memory would cause the code to succeed and give a different result.

The thing is, Turing machines don't have an infinite amount of memory. There's never a time where an infinite amount of symbols are written to the tape. Instead, a Turing machine has "unbounded" memory, meaning that you can keep getting more sources of memory when you need it. Computers are like this. You can add RAM, or USB sticks, or hard drives, or network storage. Yes, you run out of memory when you run out of atoms in the universe. But having unlimited memory is a much more useful model.


How generate n equidistant points in a n-1 dimensional space As said, i want to build a program to generate n equidistant points in an euclidian space.
From what i know

1d : all couple of points
2d : all equilateral triangles
3d : all equilateral tetrahedra
up to 3d : i suppose it's called an equilateral hypertriangle

So my problem is as follow, in a n-1 euclidian space, giving a defined point build the n-1 other in order to have an equilateral hypertriangle with a distant d between each points.

I suppose that we can start as follow with for example a 3d space.

p1 = (x1,y1,z1) fixed
p2 = (x2,y2,z2)
p3 = (x3,y3,z3)
p4 = (x4,y4,z4)
d

We start to fix p2 knowing d and p1

$d²=(x_1-x_2)^2 + (y_1-y_2)^2 + (z_1-z_2)^2$

We have 3 variables x2,y2,z2.
We can fix randomly two of them and determine the third without problem.

Then for the second point we have now 2 equations to defined it :

$d²=(x_1-x_3)^2 + (y_1-y_3)^2 + (z_1-z_3)^2$
$d²=(x_2-x_3)^2 + (y_2-y_3)^2 + (z_2-z_3)^2$

As previous, i presume that we can fix 2 variables to determine the third.

For the last point we now have 3 equations which defined it.

So for a n-1 dimensional space we have n-1 equation to defined the last point.

I don't know how to solve this kind of system composed of quadratic equation with one variable and if the process which consist to fix n-1 dimension to determine the last one lead to an equidistant hypertriangle. Moreover it exist maybe others methods with an smaller complexity and easier to implement.

I hope i was clear enough and i thank you for your help.

I assume we are working in $\mathbb{R}^n$.

First of all, observe that one regular $n-$simplex effectively determines all the others. In fact, if $S_1, S_2$ are two sets of points in $\mathbb{R}^n$ that satisfy the regularity condition, then they can be obtained from each other by composing at most an isometry and an homothetic transformation of the affine space (the converse is also true).

Therefore, it is sufficient to construct an unitary $n-$simplex centered in the origin. We visualize each vertex of the simplex $v_1, v_2, \dots v_{n+1}$ as an element of the real $n$-dimensional vector space.

Consider two vertices $v_1, v_2$ of the simplex, let $O$ be the origin and $\pi$ be the plane passing through $v_1, v_2, O$. The angle $\vartheta =\angle v_1 O v_2$ is exactly $\arccos (-1/n)$. To prove that, we observe that:

$$
0 = \left \| \sum_{i} v_i \right \|^2 = (n+1) + 2 \cos\vartheta \binom{n+1}{2}
$$

We deduce that the following hold:

$\forall i \quad \| v_i \| = 1$
$\forall i \neq j \quad \left \langle v_i, v_j\right \rangle = -1/n$

We may assume without loss of generality that $v_1, v_2$ lie on the same line, that $v_3$ lies on the same plane as the others and so on (in general, that for each $k$, $v_1, v_2, \dots v_k$ lie on the same subspace of $\mathbb{R}^n$ with dimension $k$). Therefore, we may write the vectors by coordinates as follows:

$$
\begin{array}{r c l}
\begin{array}{r}
v_1 \\ v_2 \\ \cdots \\ v_{n+1}
\end{array} &
\begin{array}{r}
= \\ = \\ \\ =
\end{array} &
\begin{array}{c c c c c c}
(x_{1,1} & 0 & 0 & 0 & \dots & 0)^T \\
(x_{2,1} & x_{2,2} & 0 & 0 & \dots & 0)^T \\
\\
(x_{n+1, 1} & x_{n+1, 2} & x_{n+1, 3} & x_{n+1, 4} & \dots & x_{n+1, n+1})^T \\
\end{array}
\end{array}
$$

The first equation uniquely determines $x_{1,1}$ and the second all the $x_{m,1}$. Now we use again the first to compute $x_{2,2}$ and with the second we determine all the remaining $x_{2, m}$.

Continuing the procedure in a similar fashion computes the coordinate values of all the vertices.


Indexed family of all unary partial computable functions Please help prove the following statement:

  The indexed family of all unary partial computable functions that have total computable extension is computable.

Definitions:

Total function - a function which is defined for all inputs of the right type, that is, for all of a domain.
A function $g$ is called an extension of the partial function $f$ if $\operatorname{Dom}(f) ⊆ \operatorname{Dom}(g)$ and $g(x) = f(x)$ for any $x \in \operatorname{Dom}(f)$, where $\operatorname{Dom}(f)$ is the domain of the function.
Let $S$ be nonempty countable set (possibly finite). Any surjective map $\nu\colon \omega \twoheadrightarrow S$ from the set $\omega$ of natural numbers onto the set $S$ is called an enumeration .
An indexed family of functions is called computable if it has at least one computable enumeration.

Additional information:

The indexed family of all unary computable functions is not computable.

Recall that a collection $\mathcal{F}$ of computable partial functions admits a computable numbering if there is a computable function $f : \mathbb{N} \to \mathbb{N}$ such that $\mathcal{F} = \{\varphi_{f(e)} \mid e \in \mathbb{N}\}$, where $(\varphi_e)_{e \in \mathbb{N}}$ is a standard enumeration of the computable partial functions.

Let $\mathcal{I}$ be the collection of computable partial functions whose domain is either $\mathbb{N}$ or some $\{0,\ldots,n\}$.

Claim: $\mathcal{I}$ admits a computable numbering.

Proof: Let $\iota(n)$ denote the program:

Input $k \in \mathbb{N}$
For each $0 \leq i < k$ simulate $\phi_n(i)$.
Simulate $\varphi_n(k)$ and output its output

Clearly, if $\varphi_n$ is total, then $\varphi_{\iota(n)} = \varphi_n$. Otherwise $\varphi_{\iota(n)}$ is defined in some initial segment of $\mathbb{N}$. Thus, $\iota$ is a computable numbering of $\mathcal{I}$.

Let $\mathcal{C}$ be the collection of partial computable functions admit a computable total continuation. It is easy to see that $\mathcal{C}$ is also the class of partial computable function admitting an extension in $\mathcal{I}$. As the domain of a partial computable function is c.e., we can then show:

Claim: $\mathcal{C}$ admits a computable numbering.

Proof: Let $\langle \ , \ \rangle$ be a standard pairing function. We define $c : \mathbb{N} \to \mathbb{N}$ by letting $c(\langle e, n \rangle)$ be the program:

Input $k \in \mathbb{N}$
Simulate $\varphi_n(k)$
Simulate $\varphi_{\iota(e)}(k)$ and output its result.

Now $c$ is a computable numbering for $\mathcal{C}$. To see this, we first note that $\varphi_{c(\langle e,n\rangle)}$ is the restriction of $\varphi_{\iota(e)}$ to the set $\operatorname{dom}(\varphi_n)$. This establishes  $\varphi_{c(\langle e,n\rangle)} \in \mathcal{C}$ for any $e, n$. Conversely, assume that $f$ is a partial computable function with a total computable continuation $g$. Let $f = \varphi_n$ and $g = \varphi_e$. Then $f = \varphi_{c(\langle e, n\rangle)}$, so we do get indeed each member of $\mathcal{C}$ in the range of $c$.


Algorithm to find the mode in a unimodal array I am given the following problem in an Algorithms class:

  Assume that you are given an array A[1 . . . n] of distinct numbers.
  You are told that the sequence of numbers in the array is unimodal, in
  other words, there is an index i such that the sequence A[1 . . . i]
  is increasing (A[j] < A[j + 1] for 1 ≤ j < i), and the sequence A[i .
  . . n] is decreasing. The index i is called the mode of A. Give an
  O(log n) algorithm that find the mode of A

I have written this draft solution as my solution but I want to make sure that this is an acceptable CORRECT solution.

My Algorithm:

FIND_MODE(A)
n = A.length
if n == 1
    return 1

mid = floor(n/2)
if A[mid] < A[mid+ 1]
    return FIND_MODE(A[1 … mid])
else
    return mid + FIND_MODE(A[mid+1 … n])

Is it this acceptable and correct pseudocode algorithm?

Is it correct that this is a Big-O(log n) algorithm?

Almost correct. Just a small correction. It should be

if A[mid] > a[mid+1]

If two consecutive elements are increasing then they are in the increasing portion of the array, so the mode is to the right. Hence the correction.


Are typical sets larger, when information is messier? Let $0\le q<p\le \frac{1}{2}$, and let $P,Q$ be two Bernoulli Random Variables such that:
$$Pr[P=1]=p ; Pr[P=0]=1-p$$ and $$Pr[Q=1]=q ; Pr[Q=0]=1-q$$
My question: Does it follow that, for any $\epsilon>0$ and $n$ as large as desired $|A_\epsilon^{(n)}(Q)|<|A_\epsilon^{(n)}(P)|$? I.e., that the Typical Set of $P$ is larger than that of $Q$?

Intuitively, I would say yes because of $q<p\le \frac{1}{2} \Rightarrow H(q)<H(p)$, and that the "messier" the information (i.e., the higher the entropy), the more elements in the Typical Set, but I've been unable to prove this.

What I've tried:

Working with typical sets size bounds, namely that:
$(1-\epsilon)2^{n(H(q)-\epsilon)}\le|A_\epsilon^{(n)}(Q)|\le2^{n(H(q)+\epsilon)}$. I was able to prove that $2^{-n(H(p)-\epsilon)}<2^{-n(H(q)-\epsilon)}$ and $2^{-n(H(p)+\epsilon)}<2^{-n(H(q)+\epsilon)}$, but that seems like a dead end.
Proving that $A_\epsilon^{(n)}(Q)\subsetneq A_\epsilon^{(n)}(P)$ but that's false.
Finding an Injective Function: $f:A_\epsilon^{(n)}(Q)\rightarrow A_\epsilon^{(n)}(P)$ but couldn't find one.

Recall that
$$
A_\epsilon^{(n)}(P) = \left\{ (x_1,\ldots,x_n) \in \{0,1\}^n : 2^{-n(h(p)+\epsilon)} \leq p^{\sum_{i=1}^n x_i} (1-p)^{\sum_{i=1}^n (1-x_i)} \leq 2^{-n(h(p)-\epsilon)} \right\}.
$$
We can rephrase the condition as follows. First, it is equivalent to
$$
2^{-n(h(p)+\epsilon+\log(1-p))} \leq \left(\frac{p}{1-p}\right)^{\sum_{i=1}^n x_i} \leq 2^{-n(h(p)-\epsilon+\log(1-p))}.
$$
Taking the logarithm, we obtain
$$
-n(h(p)+\epsilon+\log(1-p)) \leq \log_2 \frac{p}{1-p} \sum_{i=1}^n x_i \leq -n(h(p)-\epsilon+\log(1-p)).
$$
This means that
$$
|A_\epsilon^{(n)}(P)| = 2^n \Pr\left[\frac{n(h(p)-\epsilon+\log(1-p))}{\log \frac{1-p}{p}} \leq \mathrm{Bin}(n,1/2) \leq \frac{n(h(p)+\epsilon+\log(1-p))}{\log \frac{1-p}{p}}\right]
$$
In order to estimate the probability on the right, we need to use binomial tail bounds. The Chernoff bounds is a well-known upper bound, and there are almost matching lower bounds, see for example (1) and (3) in Pelekis, A lower bound on binomial tails: an approach via tail
conditional expectations. Plugging these bounds, we would get a rather accurate estimate for $|A_\epsilon^{(n)}(P)|$, which we could then compare with $|A_\epsilon^{(n)}(Q)|$, estimated using the same method.

Unfortunately, this calculational method seems like a lot of work, better done with the aid of a computer algebra system, and I am not motivated enough to actually carry it through. However, it seems likely (if not certain) that this method will be able to settle the conjecture.


Smallest Number of Strings to Distinguish $n$ Pairwise $L$-distinguishable Strings The following is a homework assignment. I am looking for criticism / feedback on my solution, and I have a specific question.

Suppose $L$ is a language over $\Sigma$, and $x_1, x_2, ... , x_n$ are
strings that are pairwise $L$-distinguishable. How many distinct
strings are necessary in order to distinguish between the $x_i$'s? In
other words, what is the smallest number $k$ such that for some set
$\{z_1, z_2, ...,z_k\}$, any two distinct $x_i$'s are distinguished,
relative to $L$, by some $z_l$? Prove your answer.

The book gives a hint, which reads as follows:

Here is a way of thinking about the question that may make it easier. Think of the $x_i$’s as points on a piece of paper, and think of the $z_l$’s as cans of paint, each $z_l$ representing a different primary color. Saying that $z_l$ distinguishes $x_i$ and $x_j$ means that one of those two points is colored with that primary color and the other isn’t. We allow a single point to have more than one primary color applied to it, and we assume that two distinct combinations of primary colors produce different resulting colors. Then the question is, how many different primary colors are needed in order to color the points so that no two points end up the same color?

I have surely addressed this question Here is my answer.

Solution: Coloring $n$ points so that no two points end up the same color requires $\lceil \log_2 n \rceil$ primary colors.
First enumerate the points using binary representations, and let each digit correspond to a primary color. Then we identify the combination of colors for a given point as all primary colors whose corresponding digit is 1. Each of the points has a unique representation, so each combination of primary colors will be unique.

What do you think of this response? Do you think it needs further explanation?
Also, I am having trouble translating this argument into the context of the original question. How can I better see that the problems are the same?

Your solution is correct but not complete.

You have not proven the correspondence to the colouring problem given as an intuition in the hint

You could say something on the lines of:- If z distinguishes x and y, we have xz belongs to L but not xy(or vice versa). This is homomorphic(? not sure about this, have to check) to colouring dots x and y with different primary colours, because indistinguishability is transitive, reflexive etc

You have only proven that you have a solution using log n strings but not that log n strings are required

This could be by contradiction. eg. assume that fewer than log n colours can be used to distinguish the dots. Represent the dots as binary strings consisting of the colours they have. Then you have fewer than log n bots required to represent n numbers in binary

IMHO you can skip the colouring and directly prove correspondence with binary strings


Cook-Levin theorem proof's requirement of $\phi_{cell}$ I'm trying to understand the Cook-Levin theorem proof, as it attempts to create a polynomial-time reduction from any NP problem to SAT (as presented in the book by Michael Sipser).

Most requirements are absolutely clear, but I don't understand why the $\phi_{cell}$ formula is required.

Of course, a tableau with improper values, such that fails $\phi_{cell}$, is broken and therefore will not "translate" correctly to the original NP problem on the other side of the reduction. We can easily "break" a tablaue by putting a $q_{accept}$ somewhere where it shouldn't, and the machine's language will change.

But I seem to miss something basic. A reduction says that if A reduces to B, then for each $w\in\Sigma^* $, $w\in A$ iff $f(w)\in B$.

The $f(w)$ part may be the "broken" tableau, but can we really call it $f(w)$? After all, such broken tableaus are never in the image of $f$.

So, why do we care about them?

We are building a reduction from problem Q (some problem in NP) to SAT.  To do that, we construct a function $f$ that maps an instance of Q to an instance of SAT.  In other words, if $w$ is an instance of Q, then $f(w)$ is a formula in CNF form.  (Recall that SAT is a decision problem whose instances are CNF formulas.)  Let's call that formula $\varphi$.  We'll remember that $\varphi$ depends on $w$.

What is the formula $\varphi$?  A formula is something that takes any assignment $x$ and assigns a truth value to it, namely $\varphi(x)$.  The way the reduction works, we interpret $x$ as a tableau, and $\varphi$ is defined so that $\varphi(x)$ will be true if $x$ is a valid tableau for the input $w$ (a valid computation of a non-deterministic Turing machine for problem $Q$ when run on input $w$).

So, $f(w)$ is not the tableau itself.  $f(w)$ is a formula that accepts valid tableaus.

Then, once we have defined $f$ (i.e., $\varphi$), we prove the following property: $\varphi$ will have a satisfying assignment if and only if $w$ is a yes-instance for problem Q.

For this to work out, the formula needs to include terms that ensure that any satisfying assignment to $\varphi$ is a valid tableau.  If you left that part out, you wouldn't be able to prove the property mentioned above, so $f$ wouldn't be a correct reduction.


Why is the log in the big-O of binary search not base 2? I am new to understanding computer science algorithms. I understand the process of the binary search, but I am having a slight misunderstanding with its efficiency.

In a size of $s = 2^n$ elements, it would take, on average, $n$ steps to find a particular element. Taking the base 2 logarithm of both sides yields $\log_2(s) = n$. So wouldn't the average number of steps for the binary search algorithm be $\log_2(s)$?

This Wikipedia article on the binary search algorithm says that the average performance is $O(\log n)$. Why is this so? Why isn't this number $\log_2(n)$?

When you change the base of logarithm the resulting expression differs only by a constant factor which, by definition of Big-O notation, implies that both functions belong to the same class with respect to their asymptotic behavior.

For example
$$\log_{10}n = \frac{\log_{2}n}{\log_{2}10} = C \log_{2}{n}$$ where
$C = \frac{1}{\log_{2}10}$.

So $\log_{10}n$ and $\log_{2}n$ differs by a constant $C$, and hence both are true:
$$\log_{10}n \text{ is } O(\log_{2}n)$$
$$\log_{2}n \text{ is } O(\log_{10}n)$$
In general $\log_{a}{n}$ is $O(\log_{b}{n})$ for positive integers $a$ and $b$ greater than 1.

Another interesting fact with logarithmic functions is that while for constant $k>1$, $n^k$ is NOT $O(n)$, but $\log{n^k}$ is $O(\log{n})$ since $\log{n^k} = k\log{n}$ which differs from $\log{n}$ by only constant factor $k$.


Why is this function computable in polynomial time? Given alphabet $\{0,1\}$, I read that the following function $f$ is computable in polynomial time relative to input $w$

$$
f(w) = w10^{|w|^2-|w|-1}
$$

i.e. $f$ can be a $TM$ that receives $w$ and outputs $w10^{|w|^2-|w|-1}$. But why is it computable in polynomial time when it has a component $0^{g(w)}$ for $g(w)=|w|^2-|w|-1$?, i.e. the size of the input is in the exponent part.

What $0^{|w|^2-|w|-1}$ is? It is "$0$" symbol repeated $|w|^2-|w|-1$ times. What is time complexity of simply outputting $0$ $|w|^2-|w|-1$ times? Clearly it is $|w|^2-|w|-1$, what is $O(|w|^2)$, i.e. polynomial of length of input.