Can quantum computers really compute a vast number of possible solutions simultaneously? This link says

  They are not constrained to stepwise calculations but, rather, can
  compute a vast number of possible solutions simultaneously—and at a
  speed that is far beyond anything we can imagine.

Is this really true? AFAIU quantum computers cannot compute a vast number of possible solutions simultaneously. A quantum computer is not a parallel computer. It is true that the wave function will exist in a superposition of states before measurement, but when we make a measurement it will collapse to a definite state. And measurements is all we can do.

From scott aaronson’s blog (https://www.scottaaronson.com/blog/)

  If you take just one piece of information from this blog: Quantum
  computers would not solve hard search problems instantaneously by
  simply trying all the possible solutions at once.

curious to know what experts think

They are not constrained to stepwise calculations

As far as I know, all QC models are stepwise.

  Under the laws of nature, the ball spins either to the right or to the left, but never in both directions at the same time. The world of quantum computing is different: Here, the ball can revolve in both directions simultaneously

I think this is the source from which comes all this “QC is a massive parallel computation”.

It is not exactly wrong to think of superposition $\frac{|0\rangle + |1\rangle}{\sqrt{2}}$ as “both $|0\rangle$ and $|1\rangle$ at the same time”, but it’s confusing. It might make you think that both things are simultaneously available for arbitrary processing, which you can fully control. As if preparing a superposition is something like creating clones.

A more precise way to think about superposition is interpreting it as uncertainty. So, less confusing statement would be “neither $|0\rangle$ nor $|1\rangle$, until the setup forces it to be definite”.


How can I understand if reduction is Karp reduction? I have a reduction and can't understand if it is Karp reduction. I want understand if my reduction is Karp reduction as well as understand how to determine which one is so.

Let I have formula $\Phi = (l_{1,1}\lor l_{1,2}\lor...\lor l_{1,k_1})\land(l_{2,1}\lor...\lor l_{2,k_2})\land...\land(l_{n,1}\lor...\lor l_{n,k_n})$

And I want to check if it is minimal CNF (decision variant of CNF minimization, one that requires to minimize amount of literal occurences). Determine if formula has an equivalent with $m$ or lower amount of literal occurences. This problem is $\Sigma^P_2$-complete. However, I have reduction:

$$Min(\Phi)=m\ge(length(\Phi)-(\overline{S(\Phi\land\overline {l_{1,1}}\land l_{1,2}\land...\land l_{1,k_1})}+\overline{S(\Phi\land l_{1,1}\land \overline{l_{1,2}}\land...\land l_{1,k_1})}+...+\overline{S(\Phi\land l_{1,1}\land l_{1,2}\land...\land\overline{l_{1,k_1}})}+\overline{S(\Phi\land\overline {l_{2,1}}\land...\land l_{2,k_2})}+...+\overline{S(\Phi\land l_{2,1}\land...\land\overline{l_{2,k_2}})}+...+\overline{S(\Phi\land\overline {l_{n,1}}\land...\land l_{n,k_n})}+...+\overline{S(\Phi\land l_{n,1}\land...\land\overline{l_{n,k_n}})}))$$

Here I use $S$ to denote $SAT$-problem.

$length(\Phi)$ counts amount of literal occurences in formula $\Phi$.

If this reduction is Karp reduction, then $\Delta^P_2 = \Sigma^P_2$ and $PH$ collapses.

But is this reduction Karp reduction, how can I determine it (general method is preferred)?

Okay, it seems, using $P^{NP}$ machine I can use $+,-,<,>,=$ operations (do not know about $\cdot,/$) for any data machine has at some step (after getting answer from oracle). If so, then I'm surprised that no one found such simple algorithm for CNF minimization.

Your reduction repeatedly calls a SAT oracle. Karp reductions only make one oracle call, and furthermore they must immediately return whatever the oracle returns (so it's like a "tail call"). So your reduction isn't a Karp reduction.

How to know if a reduction is a Karp reduction? Use the definition. A Karp reduction from a language $A$ to a language $B$ is a polytime function $f$ such that for all $x$ we have $x \in A$ iff $f(x) \in B$. If your reduction cannot be put in this form, it is not a Karp reduction.


Syntax and formal grammar of a formal language For  a formal language, I wonder what differences and relations are between its syntax and its formal grammar.

A formal grammar
is a set of formation rules
that describe how to generate the strings that belong to the formal language.

Wikipedia says that syntax

  is "the study of the principles and processes by which sentences are
  constructed in particular languages."

  the term syntax is also used to refer directly to the rules and
  principles that govern the sentence structure of any individual
  language.

So I wonder if for a formal language, its syntax and its formal grammar the the same concept? Thanks!

Syntax is a very general term that encompasses the description and
properties of physical representation of languages, i.e. of sets of
sentences intended to convey ideas, concepts, meanings, etc.  It is to be
contrasted with semantics that is concerned with what is being
conveyed.

Syntax is often thought of as structured sets of strings of symbols on
a given alphabet (sentences), but that is the simpler form. Many syntaxes have a
more complex structure, such as spoken natural language, signed
language, graphical languages, musical scores, etc.

Syntax could be thought of as just a way to describe the set of
legitimate representations, but it is usually expected to also
associate structure with these representations. This structure is the
scaffolding that is used to associate meaning (semantics) with a
syntactic construct.

Grammars are a specific way to define these sets of sentences. There
are other ways, such as automata (e.g. FA, PDA, TM), or string set
expressions (regular expressions). Some types of grammars
(Context-free in particular, but not the only one) are the preferred
medium for expressing syntax as they are complex enough to provide
structure allowing to express semantics with enough perspicuity, while
remaining simple enough to be intellectually tractable.

Regular grammar, for example, do not provide enough structure and
expressive power for general syntactic structure, but are often
adequate for the structure of simpler semantics constituants
(identifiers, numbers, morphological  strcture of natural languages).

On the other hand, while context-sensitive languages can define more
complex sets of sentences, the associated structure is usually too
complex for deriving semantics from it in a simple enough way.

Context-free grammar are convenient because they associate a tree
structure with sentences. This tree structure can be seen as an
expression in a formal algebra, from which meaning can be derived by a
convenient and well understoof mathematical tool: the homomorphism.

There are other ways of associating a tree structure with a sentence,
for example by considering derivation trees with the structure (see
mildly context-sensitive formalisms).

One could also define the syntax with automata, but this is much more
computational and less perspicuous.

Denotational vs operational aspects

The preference for grammars over automata may also be related to the
preference for denotational definitions over operational definition.
Many grammars may be seen as more denotational as they may be read as
equational definitions of syntactic structures. Though it may sometimes be
disputed, denotational definitions are perceived as closer to the
essence and mathematical properties of the defined entity, as giving a
more perspicuous understanding, more appropriate for mathematical analysis, while operational semantics are more
encumbered with technical computational or algorithmic details on the
use of these entities.

Hence, it is common practice to prefer denotational definitions as
reference, including for syntax. Operational tools (such as parsers)
are then derived for practical computational work, and have to be
proved equivalent.

Meta-language issues

Note that, when I say that a grammar "may be read as equational
definitions of syntactic structures", I assume that the grammar itself
is a sentence in a formal language (the language for writing grammar)
and that this language may be assigned one or several semantics by
appropriate means. Indeed, there is at least one well known
standardized language for writing context-free grammars which is the
Backus-Naur Form (BNF).

Actually, different semantics can often be associated with the same
syntax, though they will often be in some mathematical relation,
possibly isomorphic. This is in particular the topic of what is called
"abstract interpretations" and
"non standard interpretations" of languages.

Remark on the question

When answering the question, I did take the expression "formal
language" in a general sense of language formally defined, as often
used in mathematical context, with syntax and semantics. But the
discussion is very much the same in the case of natural language.

Now it is possible that the question was intended only for the
consideration of formal languages as simple sets of strings, as in
formal language theory.

I would tend to think that this should not change much the answer,
since even formal language theory often sees more in its formal
languages than simple set of strings. This is typically the case when
it makes a difference between strong and weak equivalence of grammars.
Furthermore, a grammar is usually only one possible way to define the
language and/or give it structure.


How exactly MOV AX will load data from RAM? Somewhere on Internet I read  : Whenever word size is greater than memory cell size, then there is a need for accessing multiple memory cell
Example:
for 16 bit processor:
MOV AX [2000]
 To transfer memory content, we need to transfer 16 bit data , so we need to access 2 memory cells
M[2000 H]
&
M[2001 H]
But I didnt get this. Why 2 cells ?
I interpreted as follows:
1) 8 bit binary code will be fetched which decoded as MOV AX.
2) From next memory location , (00 H ) will be fetched as memory is byte addressable.
3) From next memory location , (20 H ) will be fetched.
4) In IR register it is treated as ( 2000 H ) and data at (2000 H) memory location is       fetched and moved to AX register.
So why to access M[2001 H] memory location ??

I am not sure if this is actually on-topic here, but anyway.

The main memory in x86 architectures is addressed byte-wise. If you want to retrieve 16 bits from address 2000h (note that AX is a 16 register), then you will need to read 8 bits from 2000h and 8 bits from 2001h. This is why the operation needs to read "2 cells". Note that the term "cell" is not the correct one, as it typically refers to individual 1-bit memory units without addressing logic.

Note that the processor actually doesn't read the two bytes separately. Rather, the content from bytes 2000h and 2001h are fetched at the same time as the data bus to cache and main memory is >8 bits and the addresses you have here as examples are aligned, so the underlying architecture supports the parallel read.


Approach to find minimum set in one table consisting of all items in second table wondering if you can help me with the following problem.

I have one table consisting of items in each person's bag:

name  |  item1  |  item2  |  item3
____________________________________
jack  | pen     | pencil  | eraser
____________________________________
jane  | phone   | pen     | camera
____________________________________
leia  | pencil  | eraser  | glasses

I have another list with all items that can be in a bag:

pen
pencil
eraser
phone
camera
glasses

What is the best approach to find the minimum list of names who have all the items in the list? For example, in this toy example, the output would be {jane,leia}.

Your help is much appreciated. Please also let me know if I should formulate the problem differently.

This is essentially the Set Cover problem, which is NP-hard, so you should not expect an algorithm that is always both exact and efficient (polynomial-time).

If you really need the minimum set, you have to resort to algorithms that sooner or later have to explore an exponentially large solution space. You might want to cast your problem as an Integer Linear Program (ILP) and use an ILP solver, or cast it as a Satisfiability (SAT) problem and use a SAT solver. If you want to implement the algorithm yourself from scratch, I suggest you have a look into branch and bound methods.

If you don't really need the minimum cardinality set, you can just greedily pick a name that covers as many as possible uncovered items, mark them covered, and repeat, until all items are covered. This won't do too bad, in a specific theoretical sense, although in practice it may be a relatively low quality solution.


Proving Progress for STLC with Linear and Unrestricted Types In this paper Walker presents an extension of STLC with linear and unrestricted types. The proof of type soundness is left as an exercise to the reader. I encountered difficulty when attempting to prove progress (in a theorem prover):

$$ \vdash (S_1,e_1) ~\Rightarrow~ \textsf{value}{(e_1)} ~\lor~ \exists S_2 \exists e_2.~ (S_1,e_1) \rightarrow (S_2,e_2)$$

The relevant typing and evaluation relations can be found on pages 6-17 of the linked document. If we attempt to prove progress by induction on the typing derivation, we encounter the following problem: there is a typing rule for variables, but variables are not values and the evaluation relation says nothing about variables.

Now adding a variable rule to the evaluation relation is the wrong solution. For example, we don't want to reduce $(\varnothing,\mathsf{un~true})$ to $(x\mapsto\mathsf{un~true},x)$, and the immediately reduce $x$ to $\mathsf{un~true}$ by looking up its value in the store. The two solutions I am considering are (1) adding variables to the set of values; and (2) requiring that terms reduce to variables or can take a step in the statement of the progress lemma. Ideally the correction would reflect the original intention of the author. It is also possible that I am misunderstanding the paper or language.

Variables can be considered as values if the evaluation strategy is call-by-value. Otherwise said, it only makes sense to substitute a variable with a value (in call-by-value). I am unable to check if that is the case in the paper you refer to since I can't access it.


Reducing co3SAT to UNIQUE-SAT I am having trouble with this problem:

  Let N3SAT denote the non-satisfiability problem for 3CNF’s. Show that $N3SAT\leq_p
UNQ$ where in UNQ, given a CNF φ we want to know whether there is a unique satisfying assignment for φ.

I am given a hint that for every 3CNF ψ, I should construct a CNF φ (in polytime) such that ψ is a NO input for 3SAT if and only if φ is a YES input for UNQ.

What I'm having problem with is constructing the CNF from a 3CNF. Isn't a 3CNF just a case of a CNF.

So, from what I understand, once I get a CNF φ that gives a yes for UNQ, then that corresponding 3CNF will give a NO for 3SAT. So somehow the truth assignments will work out in a way that both conditions are solved.

Can someone help me out?

You are right that a 3CNF is, in particular, a CNF. The hint you give suggests that you find a reduction that, given a 3CNF $\psi$ on $n$ variables, constructs a CNF $\varphi$ such that $N(\psi) = 0$ iff $N(\varphi) = 1$, where $N(\chi)$ is the number of satisfying assignments of $\chi$. I can give a stronger hint: the reduction constructs a 4CNF $\varphi$ on $n+1$ variables such that $N(\varphi) = N(\psi) + 1$.


Multiple Source Shortest Paths in a weighted graph In an unweighted graph, we can find Multiple Source Shortest Paths using the Breadth-First Search algorithm by setting the distance of all starting vertices to zero and pushing them into the queue at the beginning of the algorithm.

However, I'm wondering if we can use the same technique to solve Multiple Source Shortest Paths in a weighted graph using Dijkstra's algorithm (for non-negative weight edges) and Bellman-Ford algorithm (when negative weight edges are allowed, and of course there is no queue here).

If I'm right, we can think in this situation as there are edges with weight equal to zero between any source and all other sources in the graph.

So, can we use this technique in a weighted graph? And why?

Yes.  Here is the trick that always works: create a new source, $s_0$, and add an edge (with length 0) from $s_0$ to each of your starting vertices.  Then, run any shortest-paths algorithm starting from $s_0$ to compute the distance from $s_0$ to each other vertex.

Your technique for BFS is equivalent to this; but this is more general and can be used with Dijkstra's algorithm, Bellman-Ford, or any other shortest paths algorithm.


Why can we assume an algorithm can be represented as a bit string? I am starting read a book about Computational Complexity and Turing Machines. Here is quote:

  An algorithm (i.e., a machine) can be represented as a bit string once
  we decide on some canonical encoding.

This assertion is provided as a simple fact, but I can't understand it.

For example, if I have an algorithm which takes $x$ as input and computes $(x+1)^2$ or:

int function (int x){
   x = x + 1;
   return x**2;
}

How that can this be represented as string using alphabet $\{0, 1\}^*$?

You already have a representation of that function as text.  Convert each character to a one-byte value using the ASCII encoding.  Then the result is a sequence of bytes, i.e., a sequence of bits, i.e., a string over the alphabet $\{0,1\}^*$. That's one example encoding.


Is it possible for a syscall to pack together different places in memory? While programming with buffers like uint8_t* in C++ I often arrive at situations on where I'm forced to do copies. For example, if I receive packets in chuncks from the world and I want to parse something big that is formed of these packets, I'd have to create a bigger buffer and store them, in this buffer, sequentially as they arrive. Then I can parse this big buffer efficiently.

Since the kernel can have virtual memory through page tables, shouldn't it be possible for someone to create a syscall that gets a pointer to a list of all these small buffers (and their sizes), and create a big virtual buffer that acts as if I've copied all the mini buffers inside it?

No, that isn't possible in general, because the page tables work at a page granularity.  If the length of every buffer is an exact multiple of the page table size, and every buffer starts at a page table boundary, you could do what you're proposing, but otherwise you can't.  Since buffers usually won't satisfy those conditions, it's not very useful to create such a syscall.

There are techniques for structuring software to avoid making copies.  However, this often requires that you restructure the code to support this.  See https://en.wikipedia.org/wiki/Zero-copy.


checking '<' for two binary numbers in a cnf-formula I want to check whether a arbitrary binary number is less or equal to another binary number in a cnf-formula. I can already construct a formula, which is not in cnf:

Lets say n and m are two-digit binary numbers:

$n = n_2 + n_1$

$m = m_2 + m_1,$

where $n_i, m_i \in \{0,1\}$ for $i \in \{1,2\}$. Then the boolean formula, which will evaluate to true if $n < m$, would be:

$(\neg n_2 \land m_2) \lor (((\neg n_2 \land \neg m_2) \lor (n_2 \land m_2)) \land \neg n_1 \land m_1)$

As described, this formula should only evaluate to true if $n < m$. I know that every boolean formula can be transformed into a cnf formula, but it seems impractical, if i have higher digit binaries.

So is there a way to construct a cnf formula, which does the same?

Yuval describes the general approach.

Let the binary representation of the two numbers be $n_1,\dots,n_k$ and $m_1,\dots,m_k$, where $n_1$ is the most significant bit.  Introduce fresh new boolean variables $t_1,\dots,t_k$.  The intention is that these will indicate the common prefix of $n,m$.

In particular, add the following clauses:

$t_{i+1} \implies t_i$ -- this ensures that $t_1,\dots,t_k$ has the form $1,\dots,1,0,\dots,0$.
$t_i \implies (n_i=m_i)$ -- this ensures that $t_1,\dots,t_k$ captures the common prefix of $n,m$
$(t_{i-1} \land \neg t_i) \implies (n_i=0 \land m_i=1)$ -- this ensures that at the first position where $n,m$ differ, $n_i < m_i$.  (For the case $i=1$, treat $t_{i-1}$ as True.)
$\neg t_k$ -- this ensures $n \ne m$

Each of these can be converted to a conjunction of CNF clauses.  For instance, the first corresponds to the CNF clause $\neg t_{i+1} \lor t_i$.  The second corresponds to $(\neg t_i \lor \neg n_i \lor m_i) \land (\neg t_i \lor n_i \lor \neg m_i)$.  The third corresponds to $(\neg t_{i+1} \lor t_i \lor \neg n_i) \land (\neg t_{i+1} \lor t_i \lor m_i)$.

Now your formula is the conjunction of all of these CNF clauses.  You obtain a formula with about $5k$ clauses.  This formula will be satisfiable iff $n<m$.


Can any recursion implementation be written as tail-recursion? Can any method that uses recursion be written as tail-recursion?

You can't rewrite all your recursive calls as tail recursive calls but you can rewrite your program in continuation passing style which is closely related and has the feature that every procedure call is a tail call (just not necessarily a tail recursive call.)

The way you do this is by recognizing that every time you make a procedure call you are implicitly specifying a return point.  Then you split your procedure into multiple procedures, each starting at a return point and ending at the next call point.  Continuation-passing style essentially makes the stack explicit.  Once the stack is explicit it is easier to apply certain optimization (like tail recursion elimination).

Example

procedure depth_first(t):
  if not-null(t):
    l = depth_first(t->left)
    r = depth_first(t->right)
    return l + r + 1
  else:
    return 0

The first step is to make every procedure take an extra parameter, k which is a continuation procedure (a procedure which you return to by calling it with the return value as its parameter).  Then you turn the procedure "inside out":

procedure depth_first(t, k):
  if not-null(t):
    depth_first(t->left,
       lambda(l):
         depth_first(t->right,
           lambda(r):
             k(l + r + 1)
  else:
    k(0)

Should you do it?  Well, if you're a compiler and you want to perform tail-recursion elimination optimizations, or generate machine code, then yes.  Otherwise probably not.  One of the joys of high level languages is that they have syntax that makes continuations much easier for humans to read and understand.  Let the compiler do what it's best at and concentrate on writing maintainable code.


Edges in and out of cycles and their relation to connectivity of the graph We know that if an edge is a part of a cycle in an undirected connected graph $G$, then if we remove that edge the graph is still connected.

Is the opposite true? If an edge is not a part of a cycle in a connected graph $G$, and we remove that edge, then the graph we get is disconnected?

P.S.: I think that it is true, and the direction for a proof is to look at one vertex it connects, and the edges that connect the vertices with it as on component, and the other end as another component, and showing that if we cut out that edge, we get two components, such that the graph is not connected. What do you think?

Yes.  Let $G$ be a graph, and suppose that the edge $ij\in E(G)$ is not on any cycle.  This implies that every path $P$ from $i$ to $j$ in $G$ uses the edge $ij$, since, otherwise, $P\cup \{ij\}$ is a cycle in $G$.  In particular, removing $ij$ from $G$ disconnects $i$ from $j$.

These kinds of edges are called bridges.


What is the expected time complexity of checking equality of two arbitrary strings? The simple (naive?) answer would be O(n) where n is the length of the shorter string. Because in the worst case you must compare every pair of characters.
So far so good. I think we can all agree that checking equality of two equal length strings requires O(n) runtime.
However many (most?) languages (I'm using Python 3.7) store the lengths of strings to allow for constant time lookups. So in the case of two unequal length strings, you can simply verify len(string_1) != len(string_2) in constant time. You can verify that Python 3 does indeed make this optimization.
Now, if we're checking the equality of two truly arbitrary strings (of arbitrary length) then it is much more likely (infinitely, I believe) that the strings will be of unequal length than of equal length. Which (statistically) ensures we can nearly always compare them in constant time.
So we can compare two arbitrary strings at O(1) average, with a very rare worst-case of O(n). Should we consider strings comparisons then to be O(1) in the same way we consider hash table lookups to be O(1)?

In order to discuss the expected time complexity of an operation, you have to specify a distribution on the inputs, and also explain what you mean by $n$.
One has to be careful, however. For example, consider the suggestion in the comments, to consider some kind of distribution over words of length at most 20. In this case, string comparison is clearly $O(1)$, since 20 is just a constant. There are several ways to avoid it:

Ask for a non-asymptotic time complexity. Since time complexity is highly dependent on the computation model, you can count (for example) the number of input memory cells accessed.

You can specify an input distribution which depends on a parameter $m$, and then ask for the asymptotic complexity in terms of $m$.

Here is an example. Given two random binary strings of length $n$, there will be roughly 4 accesses in expectation. In contrast, if the strings are chosen at random from the collection $0^i1^{n-i}$, the number of accesses will be roughly $(2/3)n$. These two distributions can be separated even if we use asymptotic notation: the algorithm runs in $O(1)$ on the first distribution, and in $\Theta(n)$ on the second.
Another issue is the meaning of $n$. Consider for example a string $0^m$, where $m \sim G(1/2)$ is a geometric random variable. When run on inputs of lengths $a,b$, the running time is $\Theta(\min(a,b))$. How should we express this in terms of $n = a+b$? One choice is to ask for the expected running time given that the input length is $n$. In this case,
$$
\mathbb{E}[\min(a,b)] = \sum_{a=1}^{n-1} \frac{(1/2)^a (1/2)^{n-1-a}}{\sum_{a'=1}^{n-1} (1/2)^{a'} (1/2)^{n-1-a'}} \min(a,n-a) = \frac{1}{n-1} \sum_{a=1}^{n-1} \min(a,n-a) \approx \frac{n}{4},
$$
so the expected running time is $\Theta(n)$.


How the concept of computer change over time? There was a time when a "computer" was a person who worked on accounts. However, machines were introduced and this profession eventually died out over time. The definition below was taken from pag 750 of volume C of the year 1893 of the OED dictionary:

Computer [...] one who computer; a calculator, reckoner a person employ to make calculations in a observatory [...]
Oxford English Dictionary. Year: 1893; Volume C. Entry computer, pag 750.

People today attribute the concept of a computer to a machine. Some even think it is wrong to say that human beings "compute", because in their head computers are only "machines". Historically we know that this is not true and commenting on this mistake is the same thing as: finding that humans are not animals, because humans are not chimpanzees.
An oberservation that I believe to be unnecessary, but it may prevent some people from making some mistakes. Human beings are not machines. I say this not because humans have feelings and machines do not, people think that way are thinking wrong. Because machines are physical objects designed by some intelligent being as a means to achieve some purpose. If you stop to think, all machines are like that and in principle nothing prevents us from having a machine that has feelings since they can be made of the same atoms as us and have structures as sophisticated as ours. Perhaps in the future, with genetic engineering, the distinction between machines and living things does not make any difference. But, that's not what I'm discussing here.
My question is this: Why do many people today only assign computing to machines only? Why is it not commonly accepted today that human beings are also computers? Since the first computers were human?

The Online Etymology Dictionary gives the first attested use of
  "computer" in the "1640s, [meaning] "one who calculates,"; this is an
  "... agent noun from compute (v.)". The Online Etymology Dictionary
  states that the use of the term to mean "calculating machine" (of any
  type) is from 1897." The Online Etymology Dictionary indicates that
  the "modern use" of the term, to mean "programmable digital electronic
  computer" dates from "... 1945 under this name; [in a] theoretical
  [sense] from 1937, as Turing machine".

It seems the word computer was given a new definition in 1945 to the more familiar programmable computer we think about today. Words change meanings all the time, it's the evolution of language and as machine computer became more popular than human computers the term computer changed as well.

Technically anything which can simulate a turning machine can be considered a computer so humans naturally can also be considered computers, but that just seems more confusing than it is helpful.


Combinatorial Optimization: Shortest distance given sets of drivers and riders Problem:

I have 2 sets, one of drivers and one of riders. All my participants need to reach one common destination. I wish to calculate the shortest combined distance in order for all participant to reach said destination. Although the goal is not to reduce the number of cars, drivers can be considered as passengers if the resulting distance is smaller.

Constraints:

Riders and drivers have distinct starting locations
All participants must reach the destination (common to all)
The riders need to be picked up by a driver
The drivers' cars have limited capacity and the capacity is individual to each car

I'm failing to understand what type of problem I'm facing, and I'm seeking some help.

Vehicle Routing Problem

I've thought of solving it as the Vehicle Routing Problem. A Capacitated Open Vehicle Routing Problem (COVRP) to be more exact. Drivers would act as the vehicle fleet and riders as the customers. A capacitated version because cars have limited seats, and an open version because drivers depart from unique positions and don't return to the "depot" but instead end on the destination.

Problem: In the VRP, not all vehicles of the fleet are used, and the remaining ones are left in their respective "depots". For my problem, I would need all participants to reach the final destination, so I need for existing vehicles to be considered as possible pick-ups for other vehicles.

I could just send the remaining drivers straight to the destination. But that wouldn't really provide a minimum distance solution to my problem, as better ones could be accomplished if the drivers could serve as customers.

Minimum Spanning Tree

As an MST problem, I could use the destination as the root and my participants (drivers and riders) as nodes. Each sub-graph originating from the root would be a cluster to be picked up by a driver.

Problem: The sub-graphs aren't guaranteed to have a driver's node in one end (to be used as a starting point and prevent doubling back on edges), and the sub-graphs may have paths with more nodes than available seats.

The capacitated MST variant introduces capacity to the solution, but it is a fixed capacity. Driver's cars have different capacities, so the MST sub-graphs would need to have individual sizes and each sub-graph would need to encompass the driver of the corresponding capacity.

Am I wrongfully categorizing my scenario as a combinatorial optimization problem?
I appreciate any help to fix the above-mentioned problems or to correctly categorize my computational problem.

Edit: If I managed to group the riders with drivers (with the use of some heuristic), then the remaining set would be drivers and their assigned passengers, or basically a list of clusters of 1+ participants.

I could then apply a capacitated MST solution to this collection. With the destination as root, the sub-graphs would be groupings of the previous clusters.
Ideally, each sub-graph would have different capacities in accordance with the seats of the containing cars.

I'm not sure that's possible, so I thought about doing a loop:

What're the most available seats in a single car?
Run the capacitated MST with that seat capacity
Get the sub-graph containing the car of the corresponding capacity
Remove all the clusters of that sub-graph from future computations
Repeat with the remaining cluster, until no more computations are possible

The problem I see arising is if the selected pivot car is in the middle of the sub-graph, meaning that it would need to double-back on edges because it wasn't a terminal node.

Still doesn't feel like a proper solution...

Thanks for the help!

These kinds of scheduling problems tend to be hard (e.g., NP-hard to solve exactly; and messy because of all of the different constraints you have).

My favorite "big hammer" for this kind of scheduling problem is to use integer linear programming, as that has been used successfully for a number of different scheduling and operations research tasks.

The best way to formulate this as an ILP problem may depend on the parameters (how many drivers and riders you have), but let me describe one illustrative approach.  Suppose each car can have up to 5 riders.  Then consider all possible ways to choose a combination $S$ of 1 driver and up to 5 riders.  For each such, compute the total distance $d_S$ of the shortest route that involves that driver picking up all riders and taking them to the destination (this might involve $5!=120$ shortest-path computations).  Now introduce a zero-or-one variable $x_S$ for each combination $S$, with the intended meaning that $x_S=1$ means we select that combination.  We require that each participant is selected exactly once; thus, for each participant $p$, we add the equality $\sum_S x_S = 1$, where $S$ ranges over all combinations with $p \in S$.  Then, we minimize the linear objective $\sum_S d_S x_S$, where $S$ ranges over all combinations.  This ensures we minimize the total distance, while ensuring every participant reaches the destination.

Then, apply an off-the-shelf ILP solver.  If the number of riders and drivers is small enough, it should find an optimal solution.  If it is taking too long, many ILP solvers will let you terminate them early and report the best solution found so far, which may be effective at finding a good but not optimal solution.

This particular formulation might work well if the number of riders is not too large.  If the number of riders is very large, you might need to consider other formulations.


What do we know about covering the edges of a graph by disjoint paths? Two related things I have heard/know of are,

(1) That there exists a polynomial algorithm to find a cover of the vertices by $k$ vertex disjoint cycles. (Can someone give a reference for this?)

(2) That its NP-complete to decide if $k$ vertex disjoint paths can cover all the vertices of a graph.

Are there edge analogues of these results?
Does using the dual graph translate these results into their edge versions?
If the line graph is a edge-to-vertex-dual then is there a vertex-to-edge-dual? (which will may be convert the question of finding a vertex cover by k vertex disjoint paths into a question of finding an edge cover by $k$ edge disjoint paths?)

You can cover the edges of a graph by cycles iff the graph is Eulerian (or has multiple Eulerian components). Notice that two cycles that share a vertex can always be combined into one cycle.


Longest Path in a directed rooted graph A directed rooted graph is defined as graph for which there exists a vertex r such that to every vertex x there is a unique path (Equivalently dfs tree with source r has only back edges and has all vertices). I need an algorithm to find the longest path in such a graph.

I know that in general longest path problem is NP-hard. I want to know whether for this special case there exists a polynomial time algorithm.

The problem falls into one of the following cases:

case (a): There is a unique path from the root to all other nodes (it means that there is only one single path from root to others; this implies that there is only one single path between any other pair of nodes too). If there is only a unique path from source to each node, then there is $O(n^2)$ number of different paths in the graph, you can just find them pick the longest one as the optimal solution using a polynomial time algorithm. You just need a DFS traversal from root and find the length of path to each leaf and choose the longest one.

case (b): But if it's a general rooted graph, i.e. there can be multiple paths from root to other nodes but there is no path from them to the root, then the following theorem holds.
This problem is NP-complete as the actual longest path problem reduces to it. The reduction is as follows. Given an instance of longest path problem $I=(G(V,E), k)$, we build an instance of your problem $I'=(G'(V \cup \{s\},E \cup \{(s,v_1),(s,v_2),...(s,v_n)\}),k+1)$ (The reduction is very strightforward, I keep it short).

In the later case, if you are just looking for a feasible solution. I suggest removing the source node from your directed graph and using the available heuristics for the longest path problem in the resulting graph. Then adding the source to that path.


Blocking because of concurrency correctness condition I am confused about a statement in The Art of Multiprocessor Programming:

Theorem 3.6.2: Let inv(m) be an invocation of a total method. If <x inv P> is a pending invocation in a linearizable history H, then there exists a response <x res P> such that H · <x res P> is linearizable.
...
This theorem implies that linearizability by itself never forces a thread with a pending invocation of a total method to block.

(The Art of Multiprocessor Programming, Herlihy & Shavit, 2008 Edition, page 58)
I understand that partial methods might need to block for correctness reasons. For example, it is reasonable to block a dequeue operation until there are elements to remove.
However, I don't see why any correctness condition (e.g. linearizability or quiescent consistency) would force an invocation of a total method to block. Is there such a case, or am I misreading the implication of the theorem?
Additionally, what does blocking mean in the context of a history? Does blocking remove an item from the history?

For your first question

  Q: However, I don't see why any correctness condition (e.g. linearizability or quiescent consistency) would force an invocation of a total method to block. Is there such a case, or am I misreading the implication of the theorem?

The short answer is that serializability is inherently a blocking property. Quoted from Section 3.3 of the paper: Herlihy@TOPLAS'90:

  A: Serializability is inherently a blocking property:
  under certain circumstances, a transaction may be unable to complete a pending operation without violating serializability, even if the operation is total. Such a transaction must be rolled back and restarted, implying that additional mechanisms must be provided for that purpose. For example, consider the following history involving two register objects: $x$ and $y$, and two transactions: $A$ and $B$.

x Read( ) A
y Read( ) B
x Ok(O) A
Y Ok(O) B
x Write(l) B
y Write(l) A

  Here, A and B respectively read x and y and then attempt to write new values to y and x. It is easy to see that both pending invocations cannot be completed without violating serializability. Although different concurrency control mechanisms would resolve this conflict in different ways, such deadlocks are not an artifact of any particular mechanism; they are inherent to the notion of serializability itself. By contrast, we have seen that linearizability never forces processes executing total operations to wait for one another.

For your second question

  Q: Additionally, what does blocking mean in the context of a history? Does blocking remove an item from the history?

A: An operation is blocked in a history if its invocation event has no matching response event.

I am not able to answer the question "Additionally, what does blocking mean in the context of a history? Does blocking remove an item from the history?".
My opinion is that it may or may not cause effects in the history. It is non-deterministic.


Why must uncommitted transactions be undone in backwards order? I have a database log where some transactions win (they are committed before crash) and some lose (not committed yet). We learned in class that the losers' actions have to be undone backwards.

Is there any reason for doing this backwards? Can anyone give a simple example of a log where forward undos would give wrong results?

Original transactions:

Insert record $r$.
Update some field $f$ of $r$.

Forward undo:

Delete record $r$.
Reverse the update to $r$ - oh wait, $r$ no longer exists! This causes an error.


How would you create a Turing machine that copies a string and prints it to the tape? For example, if I have a start state of $i$ and a string $w$, how could I create a Turing machine that would halt when the tape content is $w \Box w$? The language is $\{a,b\}$.

My initial idea was a machine that:

On $i$, moves right and changes to $p$.

On $p$, if letter read is $a$, move $n+1$ cells to the right and change to $x$.

On $p$, if letter read is $b$, move $n+1$ cells to the right and change to $y$.

On $p$, if $\Box$, change to $h$.

On $x$, write $a$, move $n$ cells to the left and change to $p$.

On $y$, write $b$, move $n$ cells to the left and change to $p$.

On $h$, halt.

However, I don't think it'll work because Turing machines aren't allowed to move more than 1 cell at a time. Any help would be appreciated.

You are pretty close, here is a TM deciding the language (pseudocode):

Check the input contains a single $\Box$,

If false, reject.

Zig-zag across the tape, check identical letters, and replace them
by $X$.

If not identical, reject.

When all the letters left of $\Box$ are marked $X$, check for remaining
letters right of $\Box$

If there are remaining letters, reject.
Otherwise, accept


Smallest integer i stored as a float such that i+1=i So I had an assignment which asked me to find the smallest integer $i$ which when represented as a float is such that $i+1=i$

My approach- By making a simple C++ program , we get $i=16777216$ or $i=2^{24}$ But if we want to do that theoretically, I am unable to arrive at this number.

So a float is 32 bit variable and the first bit represents sign of mantissa and the next 23 bits represent the number in Mantissa. The next bit represents sign of the exponent and the following 7 bits represent the value of exponent.

Now consider $2^{23}$. In Binary, it is represented as $1000,0000,0000,0000,0000,0000$ (the comma's are just to make things readable). Now if we add $1$ to it, it becomes $1000,0000,0000,0000,0000,0001$

Now we store these numbers as float in C++. Both the numbers $2^{23}$ and $2^{23}+1$ are stored as $0100,0000,0000,0000,0000,0000,00010111$ (the 1 in the end has to be scrapped in order to fit the number in 24 bits). So both of them are essentially the same for the computer.

But why does the computer give me answer as $2^{24}$?

The code that I used

#include<iostream>

using namespace std;

int main(){

    float i=1;
    while(1<2)
    {
        if(i+1==i)
            {cout << fixed << i << endl;
                break;}
        i=i+1;
    }

}

Standard “float” has a 24 bit mantissa (the highest bit doesn’t get stored because it is always 1). Therefore all integers that fit into 24 bits - all integers less than $2^{24}$ - can be represented exactly.

From $2^{24}$ onward only even numbers can be stored. So you take N = $2^{24}$, and carefully check what n+1 is according to the rounding rules.

BTW. It makes life a lot easier if you don't look at the exact bit representation of float, but just take it as "1 bit sign, 8 bit exponent, 23 bit mantissa + 1 implicit leading mantissa bit".


Algorithm for finding all the heaviest edges in a graph We have a non directed, not necessarily connected graph $G=(V,E)$, that is represented by a adjacency list, and a weight function $w:E \to R$. All edges have distinct weight. An edge is "heavy" if there exists a simple cycle in $G$ that contains it, and it has the maximal weight in that cycle. The question is to give an algorithm which finds all of the heaviest edges in $G$.

My proposed algorithm:

Create an array $A$ of size $|V|$ where every cell represents a node $v_i$ in G. Mark all nodes as 'unexplored'.
Select the node $v_1$ in $G$ and run Prim's MST algorithm from it. Modify Prim's algorithm so that when a node is reached by the MST tree it is marked as 'explored' in $A$.
Scan the array $A$ linearly from the last node encountered as 'unexplored'. Each time a node marked 'unexplored' is found, do step 2 for it.
When $A$ is traversed completely, mark the group of all the edges in all the MSTs found as $E'$.
Return $E/E'$ — this is the group of heaviest edges.

The algorithm's correctness follows from the cycle property for MSTs, and that every edge has a distinct weight.

This algorithm is as efficient as running Prim's MST algorithm on a connected non directed graph — that is $O(E + V \lg V)$ with Fibonnaci heaps.

My questions is, is this is the optimal running time for this problem? I have a feeling this can somehow be done in linear time using DFS.

In line with what Amir Nasr said in his comment above, I think the cycle property of MSTs would imply that finding a solution to your problem in linear time would find an MST in linear time.

From the Wikipedia page on MSTs and a few of the specific algorithms, it seems you can only currently do better be exploiting specific properties of your graph or using randomness.

You may find the $O(\left\vert{E}\right\vert\log{}\left\vert{V}\right\vert)$ complexity preferable to the $O(\left\vert{E}\right\vert+\left\vert{V}\right\vert\log{}\left\vert{V}\right\vert)$, and it seems that would just require a different choice of data structures or using either Kruskal's or Borůvka's.

For complexity with no $\log{}$ factors, it seems (for lack of a known general linear, deterministic, MST algorithm) you need either dense graphs, integer weights, or to use the expected linear time MST algorithm below.

https://en.wikipedia.org/wiki/Expected_linear_time_MST_algorithm


Book containing many important CS papers Several years ago my professor gave me a book that contained the most important computer science papers, including Von Neuman's paper on architectures and Dijkstra's Go-To paper. The book was an older, blue hard-cover.

Sadly, it got lost somewhere... and so I thought this might be a good place to see if anybody can point me at its editors, title, place where I can purchase it?

Does anybody know the book?

If I had to bet, I'd say:

Great Papers in Computer Science
Author: Laplante, Phillip A.
Publisher: West Publishing Co.

(this one or an older edition).

Contents

Algorithms and Data Structures

1.1 The Complexity of Theorem Proving Procedures (Stephen A. Cook)
1.2 On the Conceptual Complexity of Algorithms (J. Hartmanis, R. E. Stearns)
1.3 Quicksort (C. A. R. Hoare)
1.4 Finite Automata and Their Decision Problems (M. O. Rabin, D. Scott)

Programming Languages

2.1 The FORTRAN Automatic Coding System (J. W. Backus, et al.)
2.2 An Axiomatic Basis for Computer Programming (C. A. R. Hoare)
2.3 An Axiomatic Definition of the Programming Language Pascal (C. A. R. Hoare, N. Wirth)
2.4 The Contour Model of Block Structured Processes (John B. Johnston)
2.5 On the Translation of Languages from Left to Right (Donald E. Knuth)
2.6 Revised Report on the Algorithmic Language ALGOL 60 (Peter Naur, et al.)

Architecture

3.1 First Draft of a Report on the EFVAC (John von Neumann)
3.2 A Symbolic Analysis of Relay and Switching Circuits (Claude E. Shannon)
3.3 Alto: A Personal Computer (C. P. Thacker, E. M. McCreight, B. W. Lampson, R. F. Sproull, D. R Boggs)
3.4 The Best Way to Design an Automatic Calculating Machine (M. V. Wilkes)

Numerical and Scientific Computing

4.1 On Computable Numbers, with an Application to the Entscheidungsproblem (A. M. Turing)
4.2 On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction (A. M.Turing)

Operating Systems

5.1 Cooperating Sequential Processes (Edsger W. Dijkstra)
5.2 Solution of a Problem in Concurrent Process Control (Edsger W. Dijkstra)
5.3 A Formal System for Information Retrieval from Files (David Hsiao, Frank Harary)

Software Methodology and Engineering

6.1 No Silver Bullet — Essence and Accidents of Software Engineering (Frederick P. Brooks)
6.2 Guarded Commands, Nondeterminancy, and Formal Derivation of Programs (Edsger W. Dijkstra)
6.3 Go To Statement Considered Harmful (Edsger W. Dijkstra)
6.4 Proof of Correctness of Data Representations (C. A. R. Hoare)
6.5 On the Criteria to be Used in Decomposing Systems into Modules (David L. Parnas)
6.6 A Rational Design Process: How and Why to Fake It (David L. Parnas, Paul C. Clements)
6.7 Global Variables Considered Harmful (W. Wulf, M. Shaw)

Databases

7.1 The Theory of Joins in Relational Databases (A. V. Aho, C. Beeri, and J. D. Ullman)
7.2 Organization and Maintenance of Large Ordered Indexes (R. Bayer, E. Mccreight)
7.3 The Entity Relationship Model - Toward A Unified View of Data (Peter Pin-Shan Chen)
7.4 A Relational Model of Data for Large Shared Data Banks (E. F. Codd)

Artificial Intelligence and Robotics

8.1 Steps Toward Artificial Intelligence (Marvin L. Minsky)
8.2 Matter, Mind, and Models (Marvin L. Minsky)
8.3 Fusion, Propagation, and Structuring in Belief Networks (Judea Pearl)
8.4 Computing Machinery and intelligence (A. M.Turing)

Human-Computer Communications

9.1 Programming Considered as a Human Activity (Edsger W. Dijkstra)

History

10.1 Programming in America in the 1950s - Some Personal Impressions (John Backus)
10.2 The Evolution of Data-Base Management Systems (James P. Fry, Edgar H. Sibley)
10.3 The Evolution of the UNIX Time-Sharing System (Dennis M. Ritchie)


Prove that every two longest paths have at least one vertex in common If a graph $G$ is connected and has no path with a length greater than $k$, prove that every two paths in $G$ of length $k$ have at least one vertex in common.

I think that that common vertex should be in the middle of both the paths. Because if this is not the case then we can have a path of length $>k$. Am I right?

Assume for contradiction that $P_{1} = \langle v_{0},\ldots,v_{k}\rangle$ and $P_{2} = \langle u_{0},\ldots,u_{k}\rangle$ are two paths in $G$ of length $k$ with no shared vertices.

As $G$ is connected, there is a path $P'$ connecting $v_{i}$ to $u_{j}$ for some $i,j \in [1,k]$ such that $P'$ shares no vertices with $P_{1} \cup P_{2}$ other than $v_{i}$ and $u_{j}$. Say $P' = \langle v_{i},x_{0},\ldots,x_{b},u_{j}\rangle$ (note that there may be no $x_{i}$ vertices, i.e., $b$ may be $0$ - the notation is a bit deficient though).

Without loss of generality we may assume that $i,j \geq \lceil\frac{k}{2}\rceil$ (we can always reverse the numbering). Then we can construct a new path $P^{*} = \langle v_{0},\ldots,v_{i},x_{1},\ldots,x_{b},u_{j},\ldots,u_{0}\rangle$ (by going along $P_{1}$ to $v_{i}$, then across the bridge formed by $P'$ to $u_{j}$, then along $P_{2}$ to $u_{0}$).

Obviously $P^{*}$ has length at least $k+1$, but this contradicts the assumption that $G$ has no paths of length greater than $k$.

So then any two paths of length $k$ must intersect at at least one vertex and your observation that it must be in the middle (if there's only one) follows as you reasoned.


shortest cost tiling of path to x distance I have a distance to get to, and square tiles that have a cost and length. EX: a 1 unit block that costs 1 unit to purchase.

So if I was trying to get 10 units away. I would require 10 of the 1 unit blocks at that point for a total cost of 10.

So another example would be a distance of 10 units away except I have two tiles to pick from of [1,1], [5,4], [x,y], x = length, y = cost.

The cheapest cost would be 8, (2 of 5 blocks = 10 distance).

So, at first I thought this would be a shortest path problem, but seeing how I can re-use tiles that didn't work out the best.

I then tried to implement a rod-cutting algorithm, using the length of the rod as distance and the price for the length of cuts. This algorithm though kept trying to maximize the distance, which wasn't what I wanted.

My final method, was to divide the cost by length for each tile to find the most cost efficient tile (shown below). This worked for about 9% of my unit-tests, it was failing most because it couldn't see that it might be more cost effective to use a more expensive tile, etc.

I started with a greedy algorithm using cost / length for most efficient cost tiles, when I couldn't get that to work. I moved towards a dynamic programming algorithm using the cutting rod example.

This required a lot of hacky work, since I didn't really want the maximized value via cutting. I wanted the minimal cost value of that distance, though it also only had about a 2% success rate.

I then went into recursion, with help from another tip. Using a tiny little Tile class to help me pass variables around, this had lots of success with my self test values, but once again only had a 10% success rate.

So after trying DFS, Rod-Cutting, Recursion, and Dynamic Programming. I am lost. Did I overlook one of these algorithms?

You're heading a good direction with dynamic programming, but you haven't set up the set of subproblems quite right just yet.  Don't give up on it yet.  Instead, you should keep exploring some more candidate sets of subproblems.

The art of dynamic programming lies in picking the right set of subproblems, and then identifying a suitable recurrence relation in terms of those subproblems.  Sometimes you'll have to try several possible ways of decomposing into subproblems before you find something that works, so don't give up if your first try is not a success!

Here are some hints to help you:

When one of your inputs is an array, you can try using "the set of prefixes of the array" as your set of subproblems.  In other words, if the input is an array A[0..n-1], your subproblems can be all of the prefixes A[0..j-1], where j=0,1,2,..,n-1 (this gives n subproblems).
When one of your inputs is a non-negative integer, you can try using "the set of non-negative integers no larger than the input" as your set of subproblems.  In other words, if the input is a non-negative integer m, your subproblems can be all of the integers i, where i=0,1,2,..,m.
When you have two inputs, there are some possibilities to choose a set of subproblems.  One way is to hold one of the inputs fixed and consider all subproblems for the other input.  Another way is to choose all pairs of subproblems (if $S$ is the set of subproblems for the first input, and $T$ is the set of subproblems for the second input, use $S \times T$ as your set of subproblems).

Also, you set up your dynamic programming implementation wrong.  Your goal should not be to maximize the number of price, or to maximize anything.  You are trying to minimize the total cost (so Math.max is out of place here).  Also you will need to pass in something that describes both the cost and the length of each tile; your code doesn't show anything about that.

Finally, don't write code now.  Just figure out the ideas.  Write down a recurrence relation, and try to check whether it is correct.  Then, write pseudocode and show it is correct.  Only then should you write code.  Diving straight into code is a mistake and is getting you mixed up in implementation details before you've even worked out the conceptual material.  Also, on this site, you should not be showing us code: you should be showing us algorithms and pseudocode.  This site is about algorithms, not code (StackOverflow is the place for code).

These hints should be enough to enable you to find a solution via dynamic programming (i.e., an efficient algorithm that always finds the least-cost tiling, with reasonable running time).


Does a Vertex Cover exist? This should be a simple question, but I am a little bit confused.

A proof on page 556 of Algorithm Design says:

"Let $e=(u, v)$ be any edge of $G$. The graph $G$ has a vertex cover of size at most $k$ if and only if at least one of the graphs $G-\{u\}$ and $G-\{v\}$ has a vertex cover of size at most $k-1$."

But when I try the following example where the black ball shows a vertex cover, it seems to be faulty statement. Because $k$ remains as $k$ (not $k-1$) even after deletion of vertex $u$. Moreover, if I delete the vertex $v$, there would be no vertex cover left.

What is wrong about my deduction and example?

If you delete the vertex $v$, then there are no edges left at all, and so there is a vertex cover of size $0 \leq k-1$.

Why is the statement true in the first place? Suppose that $G$ has a vertex cover $C$ of size $k$. Since $(u,v)$ is an edge, $C$ must contain at least one of $u,v$, say $v$. I claim that $C \setminus v$ is a vertex cover of $G \setminus v$, from which the statement immediately follows. Indeed, let $(a,b)$ be any edge of $G \setminus v$. Then $(a,b) \in G$, and so $C$ contains one of $a,b$, say $a$. By construction, $a \neq v$, and so $a \in C \setminus v$.


Is there evidence that using dynamic languages has an impact on productivity? I am wondering if there are any experiments that show the existence or the non-existence of a correlation between usage of a dynamic language (such as Python, Ruby, or even languages that run on the Java platform such as Groovy, Clojure) over a static language (such as C/C++), and the difference in the productivity.

While I'm not aware of research on productivity, there's been research on comprehension. Philip Wadler has been collecting links to papers on this topic: see this post and this one.


Can we enumerate finite sequences which have no halting continuation? Note: this question has been cross-posted to Math.SE, after about a week here.

I am trying to deepen my understanding of the relationship between the Halting Problem and Godel's Completeness Theorem (not Incompleteness).

Specifically, as I understand it the Completeness Theorem guarantees a finite proof for any first-order logical statement which holds in all countable models of a first-order theory. (This is my restatement of Wikipedia's "Every syntactically consistent, countable first-order theory has a finite or countable model.")

Since the statement "Program $P_n$ (encoded by integer $n$) does not halt" can presumably be stated in first-order logic and cannot in general be proven, we need to understand why (for given $n$) it does not hold in all countable models.

Intuitively, I expect that any countable model can be encoded as an infinite program for a Turing machine, eg by listing the countable set of first-order propositions. Likewise, I expect that any such "infinite Turing machine" can be identified with a countable first-order theory, by the Church-Turing thesis plus induction.

So, just as the Completeness Theorem fails to "solve" arithmetic because of non-standard models with infinite integers (which eg satisfy otherwise unsatisfiable Diophantine equations), I'm speculating that it fails for Turing machines because of non-standard models with "infinite programs".

But by my understanding statements which are true in all models (including non-standard / infinite ones) should still be provable. So I expect that if some finite set of axioms, which "pins down" some finite set of digits of a potentially infinite program, is enough to prevent the possibility of halting, we should be able to prove it.

Or in other words, if a finite sequence does not have any continuation which encodes a halting program, that should be provable.

Does my logic hold? Or what am I misunderstanding?

The reason this is not trivially wrong by Rice's Theorem is that it's a property of the program itself, rather than the language recognized by that program, which is $\emptyset$ for the programs I'm talking about.

Not an answer, but too long to be a comment:

  Specifically, as I understand it the Completeness Theorem guarantees a finite proof for any first-order logical statement which holds in all countable models of a first-order theory. (This is my restatement of Wikipedia's "Every syntactically consistent, countable first-order theory has a finite or countable model.")

I'm not a logician so I don't know if the latter statement is true, but it's definitely not a restatement of the first statement.

The statement you quoted from Wikipedia says if you have countably many axioms and they're consistent then there exists at least one model of the theory with countably many elements.

What Godel's completeness theorem says that if a statement is true then it has a proof.

What you're missing to bridge the two is "a statement true in every countable model is true in every model."  I don't know if this is true or not (logicians would probably know off the tops of their heads).


Buchi automata in formal software verification As I am studying the application of Buchi automata in formal software verification, I am interested in the computational complexity (or links to papers) for the algorithms used to solve the problem in practice.

Let me recall the mathematical intuition behind model checking using these techniques.
Buchi automata are the automata associated to $\omega$-regular languages. You can think of these languages as the infinite version of the regular languages (infinite in the sense that they operate on infinite words). As regular languages, they enjoy closure properties under composition and intersection. It is also well known that these Automata are "isomorphic" to proposition of a logic called S1S. This is the logic of Monadic Second Order Logic (i.e. you can have quantification of on the predicates of the logic, but the elements can ranges over a finite set). S1S has the nice property of being decidable, i.e. for each preposition we can tell if it is true or not. To find if a S1S formula is satisfiable, we can find if the associated atomata has an accepting state. In Buchi automata this is done by finding cycles between the starting state and any final state.

To find a "bug" in a software we proceed like this:

we formalize our software as $\mathbb{S}$ using a S1S logic (a monaidic second order logic).
we formalize the security properties of our software in the logic $\mathbb{P}$
now we use closeness properties of $\omega$-languages, whose associated automata are equivalent to S1S logic: we build Buchi automata of $\overline{\mathbb{S}} \cap \mathbb{P}$

In this way, if the software does not comply to the security properties, the resulting automata will have at least an accepting state. In practice, the accepting state of a Buchi automata can be found by finding a cycle in the associated graph between the starting state and any final state.

I suspect in practice an algorithm for cycle detection cannot be used. This is due to the constraint that the cycle should pass from the only starting state and should pass through an accepting state, so the likelihood of finding the cycle you need might be very low. Anyway, the best algorithm for Cycle detection is solved by the Johnson Algorithm in time $O((n + e)(c + 1))$ and space bounded by $O(n + e)$).

In practice, S1S decidibility using Buchi automata might be best to be solved with s-t connectivity. For instance, NetworkX solves s-t connectivity with this algorithm
by Abdol-Hossein Esfahanian.

Am I correct?

Which graph algorithm is used in practice to solve S1S satisfiability using Buchi automata?

I have found this, but it just shows a better reduction from S1S to Buchi, and it doesn't talk about graphs.

The fastest theoretical algorithm to solve Büchi Games in game graphs is presented in  [1]  and runs in $O(n^2)$: The algorithm uses a hierarchical decomposition approach. An easier folklore algorithm with $O(mn)$ running time using just the attractor concept is mentioned.

Büchi Games on graphs should be in linear time after computing the strongly connected components of the graph.

[1] Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition. J. ACM, (2014)


Is the number of operators always one less than the number of values in an arithmetic Reverse Polish Notation expression with only binary operators? Is the number of operators always one less than the number of values in an arithmetic Reverse Polish Notation expression with only binary operators?

This question seems very trivial, but I don't know if the statement is necessarily true for all N > 1 where N is the number of values. It seems intuitively true because any expression with more than one binary operator can be expressed as a combination of two different expressions through induction, but I'm not very confident.

RPN expressions have stack semantics: a value pushes a number onto the stack, whereas a binary operator pops two values and pushes one back, for a net loss of one element. At the start of an expression the stack is empty, and at the end there is exactly one value – the result.

Now let $V$ be the number of values in the expression, and $B$ be the number of binary operators. Then at the end of the expression, the stack contains $V-B$ values. Since there should be exactly one value remaining, we conclude that $V-B = 1$, or $B = V-1$.

Another way to see this is using structural induction. As you mention, every expression is either a value or is obtained from two expressions combined using a binary operator. Let's prove by induction on the number of values and operators appearing in the expression that $V = B+1$ (in the terminology of the preceding section).

When the expression consists of just a value, $B=0$ and $V=1$, so $V = B+1$. When the expression consists of a binary operator together with two other expressions $E_1,E_2$, we have $V = V(E_1)+V(E_2)$ and $B = B(E_1)+B(E_2)+1$ (I hope the notation is clear). By induction, $V(E_1) = B(E_1)+1$ and $V(E_2) = B(E_2)+1$, so
$$ V = V(E_1) + V(E_2) = B(E_1) + 1 + B(E_2) + 1 = B + 1. $$


Calculate Miss rate of L2 cache given global and L1 miss rates If I have a Global miss rate of all caches of a total of 5.41% and the miss rate of a single level cache of 9.13%, how can I effectively calculate how much the second level cache miss rate need to be?

I found this where it says that the Local miss rate equals misses in a cache divided by the total number of memory accesses to this cache (Miss rate L2) and Global miss rate equals misses in a cache divided by the total
number of memory accesses generated by the CPU
(Miss Rate L1 x Miss Rate L2).

So if I divide 5.41% / 9.13% it  equals 0.5926% for my second level cache. Is this assumption correct?

You would only access the next level cache, only if its misses on the current one. Therefore the global miss rate is equal to multiplication of all the local miss rates.

0.0541    = L2 misses * 0.0913
L2 misses = 0.0541/0.0913 = 0.5926
L2 miss rate = 59.26%

In your answer you got the % in the wrong place.


Develop the context free grammar to match this language (puzzle) This is a puzzle type question which asks to create a context-free grammar to match this language:

{ x#w | x,w are in {a,b}*, and w contains the reversal of x as a substring }

So some example strings to try:
    #, a#a, b#b, ab#ba, ab#aaabbba

Does anyone have any advice on how to get better at these types of problems?  I am generally a good problem solver, but have trouble developing grammars for languages for some reason.  I am completely stuck on this question.  Here is my attempt:

S --> TR
T --> aTa | bTb | #R
R --> RR | 0 | 1 | empty

My guess is that we want to define the left side of the string in terms of the right side of the string.

Edit:  As far as I can tell, the above answer seems to be correct now.  Only took me an hour to figure out!

X --> Xa | Xb | Y

Y --> aYa | bYb | #Z

Z --> Za | Zb | empty

Y is the part that handles the string reversal. X and Z handle junk to the right and left of the reversal of x.


Doubt regarding the implications of a 2-SAT constraint Consider an example 2-SAT instance with the constraint (x1 ∨ x2).
This CNF has these two implications:
¬x1→x2 and ¬x2→x1.
"They actually mean, if x1 is false then x2 must be true, and if x2 is false then x1 must be true, respectively. Any other case would make the 2-sat problem unsatisfiable."
My doubt is regarding this statement. I can understand the above written two implications, but I don't understand how only those two values of x1 and x2 make this 2-SAT instance satisfiable. Clearly setting both x1 and x2 to true can also satisfy this constraint.
I don't see that case being captured in the two implications written above.
Can someone explain this to me? Apologies if this is a stupid question, I haven't formally studied logic.

$A\rightarrow B$ doesn't necessarily mean that $B\rightarrow A$. In your example, "$x_1$ is false then $x_2$ must be true" doesn't imply that if $x_2$ is true, $x_1$ must be false. Therefore, setting both $x_1$ and $x_2$ to true would not contradict the statement.
Also, as a side note, $\lnot x_1\rightarrow x_2$ is logically equivalent to $\lnot x_2 \rightarrow x_1$, so the two implications you described are identical.


Reduction from Clique to IS degree at most 4 This is from the Algorithms textbook by Dasgupta,C. H.Papadimitriou,andU. V. Vazirani question 8.6 (b) that asks:

Edit:

And missing from the pic as @Nathaniel points out in his answer below:
"3SAT remains NP-complete even when restricted to formulas in which
each litteral appears at most twice".

My reduction from Clique:
Definition of clique: fully connected graph/subgraph
So given G=(V,E) and a goal g it returns a clique of size g fully connected.
The complement graph G’ would contain an IS of size g of the same vertices.
So given a graph G, with degree at most 4, as input to Clique, the largest possible clique would be of size 5 vertices per the  definition.  Let's assume g=5 as input to the Clique problem.
Make the complement graph G’ =(V, E’) where uv in E’ not in E and call ISdeg4 on G’ with g=5.
If there is an IS of size g=5 in G’, then those 5 vertices make up a clique in G so return that to Clique.
Else returns no which I can return to Clique.
ISdeg4 is in NP:
Returns a set of vertices which are an IS.
In O(n+m) I can check that none of the v's in the IS have an edge to another v in the IS.
So ISdeg4 can be used to solve Clique problems for G=(V,E) with degree at most 4.
Edit:
The above is not a solution since the reduction from Clique to ISDeg4 only solves a subset of Clique problems where an input G=(V,E) is at most degree 4.
Thus, I want to know if anyone has a reduction from a known NP-Complete graph problem rather than 3SAT-> IsDeg4 which I was able to understand after seeing the solution given by my teacher.

As you stated, this is not a correct reduction, because you would need to solve Clique for any graph (or prove that Clique with graphs of degree at most 4 is $NP$-complete).
Actually, the question 8.6.b stands true if the graph have degree at most 3. I think the intention of the author for solving this exercice is to use the remark stated at the beginning of the exercice (which you cropped): "$\textsf{3SAT}$ remains $\textsf{NP}$-complete even when restricted to formulas in which each litteral appears at most twice".
You should then make a reduction from $\textsf{3SAT-2LITmax}$ (a convenient name I came up for the problem I just described), using the same kind of reduction to prove $\textsf{NP}$-hardness of $\textsf{IS}$ from $\textsf{3SAT}$.


Merge Sort meaning of a bit part of code I am studying this part for a merge sort implementation:

void mergeSort(int arr[], int l, int r) {
if (l < r)
{
    // Same as (l+r)/2, but avoids overflow for
    // large l and h
    int m = l+(r-l)/2;

    // Sort first and second halves
    mergeSort(arr, l, m);
    mergeSort(arr, m+1, r);

    merge(arr, l, m, r);
}}

What is the meaning of:

    // Same as (l+r)/2, but avoids overflow for
    // large l and h
    int m = l+(r-l)/2;

in the code?
Why can't I use (l+r)/2? (I didn't understand the comment)

Because of integer overflow, (l+r)/2 won't  actually compute the midpoint like we want in some special cases.  See
 https://stackoverflow.com/q/17358806/781723 and https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html for details.


Is the below language Non R.E? $L_0=\{\langle M,w,0\rangle\mid M \text{ halts on } w\}$

$L_1=\{⟨M,w,1⟩\mid M \text{ does not halts on } w\}$

Here $\langle M,w,i \rangle$ is a triplet, whose first component $M$ is an encoding of a Turing Machine, second component $w$ is a string, and third component $i$ is a bit.

Let $L=L_0 \cup L_1$. Is $L$ non R.E ?

After seeing the question I was able to figure out that there are some strings that do not belong to $L_0$ as well as $L_1$.

Like, lets take the case for $L_0$ and a string $001\dots10−01−1$, ("$-$" shown for notation purpose only) where the  first component describes a TM $M$ followed by input "$w=01$" and last bit "$1$". Now suppose M halts on "$01$". Still the given input is not in $L_0$ as the last bit is "$1$" and not "$0$" as required by $L_0$. So, this input must be in $L_1$. But since $M$ halts on $w$, this input is not in $L_1$ either.  So there are infinite strings like these. I am not able to prove that these infinite  set of strings are not r.e.

Is there any method to solve these kind of problems? I am not able to master these kind of problems.

Please someone help.

Assume that $L$ is r.e. and $M_L$ recognizes $L$. Given $\langle M,w \rangle$, $M$ on $w$ either halts or not. This means that either $\langle M, w, 0 \rangle$ or $\langle M, w, 1 \rangle$ must be in $L$. Then using a universal Turing machine start to run/simulate $M_L$ on both inputs $\langle M, w, 0 \rangle$ and $\langle M, w, 1 \rangle$, simultaneously, say one step at a time for each input. After each step check if $M_L$ halts on at least one input. Since $L$ is r.e. and exactly one of $\langle M, w, 0 \rangle$ and $\langle M, w, 1 \rangle$ belongs to $L$, $M_L$ must eventually halt on one of them. Depending on which input $M_L$ halts, you can tell if $M$ halts on $w$. This decides the Halting problem and hence $L$ is not r.e.


LL(1) CFG for triple amount of b's compared to a's? I would like to construct a LL(1) context-free grammar for a formal language $A$ = "strings where the amount of character b is exactly triple compared to the amount of character a" for $\Sigma = \{a,b\}$.

I've tried to figure it out so that if we consider a string $w$ to have one a, then the acceptable presentations for $w$ considering language $A$ would be abbb, babb, bbab and bbba.

But how do I build the CFG rules for that? I have tried something like $$S \rightarrow A$$ $$A \rightarrow \epsilon | aAbbb |baAbb | bbaAb | bbbaA$$ but I think it's not very good because at least I cannot build an LL(1)-parser out of it (which would be good) because of ambiguity. And it doesn't quite work out for a string like bbbbbbaa $\in A$.

Is it possible to build a CFG for this language that can be parsed using a LL(1) parser?  If not, why not?

I believe that any string able to be represented by a CFG can also be parsed in LL or LR. That is just one of the features of CFG's. The grammar you have originally written can be parsed using LL as the upper-case $A$ will act always as your left-most variable to be expanded and simplified.

I think your problem with constructing the grammar can be solved by also including rules in which the lower-case and upper-case $a$'s are switched, though, that is a rather clunky solution.

$S \rightarrow A$

$A \rightarrow \epsilon | baAbb | bAabb | bbbaA | bbbAa | bbaAb | bbAab | aAbbb| Aabbb$


How do contemporary processors differ from a pure von Neumann architecture? So I never really understood the von Neumann architecture, and have started to revise it as I wasn't in school during the lessons of the CPU. Can't really get help through my teacher as they wont respond to their email.

I have learnt about the von Neumann architecture, and now I need to know how the architecture differs from a contemporary processor.

I know that contemporary processors sometime use a mixture of Harvard and von Neumann architecture by using Harvard for the communication between the control unit and caches though for cost effective reasons von Neumann is used between the main memory and cpu.

The specification point wants to know how it differs though, and I will be very thankful for any responses that might answer the question.

Thanks!

Well I think I may have answered my own question, the specification just wanted to know how it differs from the pure von Neumann architecture. It differs as contemporary processors use a mixture of architectures from Harvard and von Neumann for many reasons (mainly cost) and where speed advantages outweigh the complexity costs.

Contemporary processors use a mixture of both von Neumann and Harvard architecture, which differs from a pure von Neumann architecture by using von Neumann architecture for the main memory to the CPU and Harvard for the control unit and caches.


Difference between Recursion Tree & Binary Tree What's the difference? is a Recursion tree private case of Binary tree?

A binary tree is a rooted tree where every internal node has at most two children.
A recursion tree is a rooted tree which traces the execution of a recursive procedure. It need not be binary.


Can a Turing Machine decide if an NFA accepts a string of prime length? I want to know if the following problem is decidable:

Instance: An NFA A with n states

Question: Does there exist some prime number p such that A accepts some string of length p.

My belief is that this problem is undecidable, but I can't prove it. The decider can easily have an algorithm to figure out if a particular number is prime, but I don't see how it would be able to analyze the NFA in enough detail to know exactly what lengths it can produce. It could start testing strings with the NFA, but for an infinite language, it may never halt (and thus not be a decider).

The NFA can easily be changed to a DFA or regular expression if the solution needs it, of course.

This question is something I've been pondering as a self-made prep question for a final I have coming up in 2 weeks.

The lengths of the strings accepted by a DFA form a semilinear set (like in Parikh's theorem for context free languages), the description of those isn't too hard to come by (essentially splice up all possible cycles of the automaton), and by Dirichlet's theorem any arithmetic progression of the form $a + b k$ with $\gcd(a, b) = 1$ contains an infinitude of primes.

Pulling the above together gives an algorithm to check if your regular (or even context free language) contains strings of prime length. Definitely not a simple question, IMVHO...


What is an approximation factor for the Greedy Motif Search algorithm? What is approximation factor for the Greedy Motif Search algorithm?
I couldn't find an answer to my question except for the fact that the algorithm has a unknown aproximation factor. I'm not a native speaker and there is almost nothing about it available in my first language which makes it really hard to even understand the definition of the "approximation factor" which may lead to this question that could be rather obvious to answer.

A possible algorithm is shown on page 4:
http://veda.cs.uiuc.edu/courses/fa08/cs466/lectures/Lecture5.pdf

I know that there isn't a known approximation factor because sources like the book "An Introduction to Bioinformatics Algorithms" are stating it.
I haven't really formed thoughts on it, because I'm not certainly sure what the definition of approximation factor is in a case like this. What I mean is: "The approximation ratio, or performance guarantee of algorithm A is defined as its maximum approximation ratio over all inputs of size n".
I would've thought that it may be unknown due to the fact that we could have a input of infinite, which is probably not the right thought in this regard. Another thought I had was that the algorithm has no lower bound for the optimal solution.

Quoting Master’s Thesis in Computer Science by Finn Rosenbech Jensen0, Dec. 2010, Greedy Motif algorithm approximation factor, using common superstring1 and its linear approximation2, was proved it cannot be better then 2.
Using proof by Kaplan and Shafir3 author shows that $\mid t_{greedy}\mid = 3.5 * OPT(S)$.

[0]: Master thesis by Rosenbech Jensen
[1]: Tarhio, J. and E. Ukkonen (1988).  A greedy approximation algorithm for constructing shortest common superstrings.Theor. Comput. Sci. 57(1),131–145.
[2]: Blum,  A.,  T.  Jiang,  M.  Li,  J.  Tromp,  and  M.  Yannakakis  (1994,  May).Linear approximation of shortest superstrings.   InProceedings of the23rd Annual ACM Symposium on Theory of Computing, pp. 328–336.
[3]: Kaplan, H. and N. Shafrir (2005).  The greedy algorithm for shortest su-perstrings.Inf. Process. Lett. 93(1), 13–17.


K-Clique in Connected Graphs A question about the clique problem (specifically k-clique). Is there any algorithm that takes advantage of the properties of connected graphs to find cliques of a given size k, if such cliques exist?

As pointed out in the previous answer, you cannot do very well if you simply assume that your input is a connected graph. However, you can do better if you make certain assumptions on your graph's structure. That is, one can ask: given a class of graphs $\mathcal G$, will the clique problem be solvable in polynomial time, assuming that all inputs are contained in $\mathcal G$?

The answer turns out to be positive for a nice class (or should I say classes) of graphs: graphs whose treewidth is bounded by a constant.

Without getting into too much detail (see http://en.wikipedia.org/wiki/Tree_decomposition for more details), the tree-width of a graph is a measure of how much it "resembles" a tree. Trees have a treewidth of 1, whereas cliques have a treewidth of $n-1$ (where $n$ is the number of vertices).

The clique problem is $\mathcal O(t^t n)$ on graphs whose treewidth is at most $t$.

Treewidth is believed to be the "right" measure for graphs problems (although more complex measures do exist): Courcelle's Theorem (see http://en.wikipedia.org/wiki/Courcelle's_theorem) states that any graph property that can be succinctly expressed via some logical parameters can be solved in polynomial time on graphs with treewidth bounded by a constant. This includes vertex cover, clique, independent set, and many others.

This means that many NP-hard graph problems are fixed parameter tractable, with treewidth being the parameter.

Hope this helps.


Can generalized Turing machines compute all reals? Super-recursive algorithms are theoretical super-recursive algorithms are a generalization of ordinary algorithms that are more powerful, that is, compute more than Turing machines.

In this entry it is said:

  A symbol sequence is computable in the limit if there is a finite, possibly non-halting program on a universal Turing machine that incrementally outputs every symbol of the sequence. This includes the dyadic expansion of π but still excludes most of the real numbers, because most cannot be described by a finite program. Traditional Turing machines with a write-only output tape cannot edit their previous outputs; generalized Turing machines, according to Jürgen Schmidhuber, can edit their output tape as well as their work tape

Does that mean that, theoretically, generalized Turing machines, cannot compute all reals? Can generalized Turing machines do (fully) hypercomputation (theoretically)?

(I know that there is strong evidence against hypercomputation. I'm asking this only from a theoretical perspective)

Any machine model in which a machine can be described by a string over a fixed alphabet can only compute countably many things. Since there are uncountably many real numbers, all of these machine models fail to compute almost all real numbers.

In fact, the alphabet need not be fixed. It is enough that the alphabet is taken from some countable set of finite alphabets, for example $\{1,\ldots,n\}$ for every $n$.


How to detect stack order? We take the sequence of integers from $1$ to $n$, and we push them onto a stack one by one in order. Between each push, we can choose to pop any number of items from the stack (from 0 to the current stack size).

Every time we pop a value from the stack, we will print it out.

For example, $1,2,3$ is printed out when we do push, pop, push, pop, push, pop. $3,2,1$ comes from push, push, push, pop, pop, pop.

However, $3,1,2$ is not a possible printout, because it is not possible to have $3$ printed followed by $1$, without seeing $2$ in between.

Question: How can we detect impossible orders like $3,1,2$?

In fact, based on my observation, I have come out a potential solution. But the problem is I can't prove my observation is complete.

The program that I wrote with the following logic:

When the current value minus the next value is larger than 1, a value between current and next cannot appear after next. For example, if current=3 and next=1, then the value between current (3) and next (1) is 2 which cannot appear after next(1), hence $3,1,2$ violates the rule.

Does this cover all cases?

I couldn't understand your approach exactly (Seems it's correct), but there is a simple rule for impossible orders: The order is impossible $iff$ there is $a_i,a_j,a_k$ such that $a_i > a_k > a_j$ and $i<j<k$. To such a $a_i,a_j,a_k$ we say bad triple.

Why? First you should prove that if there is bad triple then the sequence is impossible, but this is simple and I'll leave it as exercise (middle number couldn't pop sooner than bigger except smaller poped before all of them).

Second you should prove all impossible orders have at least one bad triple, Assume you have a sequence without any bad triple, you could find the order of push and pop so it's not impossible sequence. For reconstructing the push and pop orders just use naive approach (operation is pop while you iterating over consecutive numbers), but for formal proof (for simplicity) you could use induction, assume for all sequences of length $m$ if there isn't bad triple they aren't impossible. For sequence of length $n$, you can set operations as pop (start from end of sequence), while encountering with increasing consecutive numbers, now you have a sequence of length $m$, with $m < n$, without bad triple, so you can reconstruct push and pop for this sequence, so original one wasn't impossible. start of induction is sequence of length 3.


N-gram language model question I have this question I found regarding n-gram modelling in the textbook Speech and Language Processing:

Suppose we didn't use the end symbol </s>. Train an unsmoothed bigram grammar on the following corpus without using the end-symbol </s>.

<s> a b
<s> b b
<s> b a
<s> a a

Demonstrate that your bigram model does not assign a single probability distribution across all sentence lengths by showing that the sum of the probability of the four possible 2 word sentences over the alphabet {a, b} is 1.0 and the sum of the probability of all possible 3 word sentences over the alphabet {a, b} is also 1.0.
Note:
<s> means beginning of sentence.
</s> means end of sentence.
Speech and Language Processing, Daniel Jarafsky and James H. Martin, 3rd ed., Exercise 3.5, p.55

My attempt was:
Two word sentences:
P(a | b) = count(b a) / count(b) = 1 / 4
P(b | a) = count(a b) / count(a) = 1 / 4
P(a | a) = count(a a) / count(a) = 1 / 4
P(b | b) = count(b b) / count(b) = 1 / 4

sum = 1
but when I get to 3 word sentences:
P(a | a, a) = count(a a a) / count(a) = 1 / 64
Now, you get 8 three word sentences which sums to 8 / 64
This is where I am getting lost. I need some pointing in the right direction.

For these 2-word sentences, notice that the original equation for the MLE approximation of the probabilities of the bigram is:
$$P(w_i|w_{i-1}) = \frac{C(w_{i-1}w_i)}{\sum_w{C(w_{i-1}w)}} = \frac{C(w_{i-1}w_i)}{C(w_{i-1})}, $$
where the denominator $C(w_{i-1})$ only equals the count of $w_{i-1}$ iff there is an end-symbol $\text{</s>}$, otherwise the number of times $w_{i-1}$ appears at the end of the sentence has to be subtracted from its count. Therefore, the "count" function you are using in the denominator is wrong, and the true probabilities in your particular corpus are:
$$\begin{equation}
\begin{split}
P(a|a) &= \frac{C(aa)}{C(a)} &= \frac{1}{2} \\
P(b|a) &= \frac{C(ab)}{C(a)} &= \frac{1}{2} \\
P(a|b) &= \frac{C(ba)}{C(b)} &= \frac{1}{2} \\
P(b|b) &= \frac{C(bb)}{C(b)} &= \frac{1}{2} \\
P(a|\text{<s>}) &= \frac{C(\text{<s>}a)}{C(\text{<s>})} = \frac{2}{4} &= \frac{1}{2} \\
P(b|\text{<s>}) &= \frac{C(\text{<s>}b)}{C(\text{<s>})} = \frac{2}{4} &= \frac{1}{2} \\
\end{split}
\end{equation}$$
and now the sum of the probabilities of all possible 2-word sentences with this vocabulary becomes equal to 1:
$$\sum_{w, v\in\{a, b\}^2}P(\text{<s>}wv) = \sum_{w, v\in\{a, b\}^2} P(w|\text{<s>})\cdot P(v|w) = \sum_{w, v\in\{a, b\}^2} \frac{1}{4} = 1 .$$


Version of knap sack problem The are cuisenaire rods with N differnt lengthes $x_1,x_2,...,x_n$ (each length is a natural number), the number of the Cuisenaire rods is unlimited. Given a natural number B. you should tell if you can pick a bunch of Cuisenaire rods with exactly the length of B.

  for example: if the cuisenaire rods are $3,11,19$ and $B=20$ so you should return true because $3+3+3+11=20$. but for $B=19$ return false.

I made a $(N+1)\times(B+1)$ table named "opt", checked for all $0\leqslant i\leqslant n$ and for all $0\leqslant b\leqslant B$ if i can get a length using the lengthes $x_1,x_2,...,x_i$ and weights $0\leqslant b\leqslant B$

For the given example he output should be (this is my output also)

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0
0 0 0 1 0 0 1 0 0 1 0 1 1 0 1 1 0 1 1 0 1
0 0 0 1 0 0 1 0 0 1 0 1 1 0 1 1 0 1 1 1 1

My idea:

fill in with zeros the first line and the first column, i.e opt[0][b]=0 for all b and opt[n][0]=0 for all n

Here  cuisenaire={0,3,11,19} is array with the cuisenaire lengths

 for n=1 to N+1
        for b=1 to B
            opt[n][b]=opt[n-1][w];//copy the previos row
            if w modulu cuisenaire[k]=0
                opt[n][w]=1;

            if w >=cuisenaire[n] and n>1 and (w+cuisenaire[n]-1)module (cuisenaire[n-1])=0)
                opt[n][w]=1;

my Idea works only for small B's $\implies $ wrong idea but maybe close, e.g for $B=100$ and cuisenaire={0,13,19,29} my idea doesn't work
can't think on recursive idea

The problem is similar to coin denomination with infinite number of coins available.

Let me know if this works ... http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

For every length which you encounter, you have two options, you can either use this rod or ignore this rod length and continue to the next one. In both the cases you can check if you could reach the target. If you can return true, else false.

So lets say you have a function canFindTarget( inputArray[], idx , sum ) which returns true if you can make sum using inputArray[0..idx-1] else false. Your answer would be canFindTarget( inputArray[], idx-1, sum ) || canFindTarget( inputArray[], idx, sum - inputArray[idx - 1]).


Is there a name for this graph transformation (remove a 'thru' node) I have a directed graph, eg:

$$A\to B\to C$$

$A$ and $C$ may have multiple in- and out-edges, but B has exactly one in- and one out-edge.

I want to remove node $B$ and replace the edges $(A,B)$ and $(B,C)$ with a single edge $(A,C)$.

Is there a name for this operation?  In particular a name or algorithm for finding all nodes such as $B$ and removing them from the graph.

You're contracting the edge $(A,B)$ (or, equivalently, $(B,C)$).

To contract an edge $(x,y)$ is to delete the vertex $y$ and make all its neighbours except $x$ itself be neighbours of $x$ instead.


Average case algorithm analysis using Kolmogorov Incompressibility Method The Incompressibility Method is said to simplify the analysis of algorithms for the average case. From what I understand, this is because there is no need to compute all of the possible combinations of input for that algorithm and then derive an average complexity. Instead, a single incompressible string is taken as the input. As an incompressible string is typical, we can assume that this input can act as an accurate approximation of the average case.

I am lost in regard to actually applying the Incompressibility Method to an algorithm. As an aside, I am not a mathematician, but think that this theory has practical applications in everyday programming.

Ultimately, I would like to learn how I can deduce the average case of any given algorithm, be it trivial or complex. Could somebody please demonstrate to me how the method can be applied to a simple algorithm? For instance, given an input string S, store all of the unique characters in S, then print each one individually:

void uniqueChars(String s) {
    char[] chars = chars[ s.length() ]
    int free_idx = 0;

    for (int i = 0; i < s.length(); i++) {
       if (! s[i] in chars) {
          chars[free_idx] = s[i]
          free_idx++;
       }
    }

    for (int i = 0; i < chars.length(); i++) {
        print (chars[i])
    }
}

Assume a linear search for checking whether the array contains an element.

The above code snippet is only for the sake of argument.
Better algorithms by which the theory can be demonstrated are acceptable, of course.

I asked this question on StackOverflow (https://stackoverflow.com/q/24619383/3813812) back in July, 2014, and have received a few helpful comments but not a definite answer. As one of the commenters pointed out, this question is better suited for Computer Science StackExchange, so I ask here today.

Some literature that I have reviewed includes:

An Introduction to Kolmogorov Complexity and Its Applications, by Ming Li and Paul M.B. Vitányi
https://www.cs.duke.edu/~reif/courses/complectures/Li/KC-Lecture1.pdf
http://www.detectingdesign.com/PDF%20Files/Kolmogorov%20Complexity%202.pdf

Among a few other resources that I do not have links to on hand.

If my understanding of the applicability of Kolmogorov complexity is inaccurate or what I ask is impractical, I would appreciate a statement with regard to the fact.

The idea of the incompressibility method is that an incompressible input satisfies certain properties that can be helpful in the analysis. In your case, the complexity of the algorithm depends on how many characters appear in the string. When processing the $k$th character, the "running time" (or rather its proxy, the number of comparisons when checking the list) is $\approx \alpha_k/2$ comparisons on average, where $\alpha_k$ is the number of different characters that have been seen so far. In order to estimate $\alpha_k$, note that we can encode the first $k$ characters using roughly $8\alpha_k + k\log \alpha_k$ bits, and we deduce that $8\alpha_k + k\log_2 \alpha_k \geq 8k$. Hence unless $k$ is very small, $\alpha_k$ has to be very close to $256$, and we can deduce that there are on average $128$ comparisons per character. We can use the inequality to determine how large $k$ needs to be, and also what happens when $k$ is small.

The reason we are trying to count the exact complexity in the case of your algorithm is that its worst-case and best-case running times are both $\Theta(n)$. We used incompressibility to estimate $\alpha_k$, which can also be estimated directly using probabilistic methods, but the incompressibility calculation is probably simpler. Still, incompressibility doesn't obviate the need to analyze the algorithm probabilistically – it just makes the analysis more tractable in some cases.


Why do neural networks seem to perform better with restrictions placed on their topology? Fully connected (at least layer to layer with more than 2 hidden layers) backprop networks are universal learners. Unfortunately, they are often slow to learn and tend to over-fit or have awkward generalizations.

From fooling around with these networks, I have observed that pruning some of the edges (so that their weight is zero and impossible to change) tends to make the networks learn faster and generalize better. Is there a reason for this? Is it only because of a decrease in the dimensionality of the weights search space, or is there a more subtle reason?

Also, is the better generalization an artifact of the 'natural' problems I am looking at?

Fewer nodes/edges (or edges with fixed weights) means that there are fewer parameters whose values need to be found, and this typically reduces the time to learn. Also, when there are fewer parameters, the space that can be expressed by the neural network has fewer dimensions, so the neural network can only express more general models. It is thus is less capable of over-fitting the data, and hence the models will seem more general.