How to work out physical address corresponding to logical address? I am looking to calculate the physical address corresponding to a logical address in a paging memory management scheme. I just want to make sure I am getting the calculation right, as I fear I could be wrong somewhere.

So, the data I have is as follows:

The logical address: $717$
Logical memory size: $1024$ bytes ($4$ pages)
Page Table:

\begin{array}{| c | c |}
\hline
Page\ Number & Frame\ Number\\ \hline
0 & 5\\ \hline
1 & 2\\ \hline
2 & 7\\ \hline
3 & 0\\ \hline
\end{array}

Physical memory: $16$ frames

So, with $1024$ bytes in the logical memory, and $4$ pages, then each page is $256$ bytes.

Therefore, the size of the physical memory must be $4096$, right? ($256 \times 16$).

Then, to calculate the logical address offset:

$$1024 \mod 717 = 307$$

Is that how we calculate the offset?

And, we can assume that $717$ is in page $2$ ($\frac{1024}{717} = 2.8$)?

So, according to the page table, the corresponding frame number is $3$.

And so to get the physical address, we multiply the frame number and page size?

$$2 \times 256 = 768$$

Then, do we add the offset, like so:

$$768 + 307 = 1,075$$

Thank you for taking the time to read. If I don't quite have this correct, would you be able to advise on the correct protocol to calculating this?

You are correct in your reasoning that the pages are $256$ bytes and that the physical memory capacity is $4096$ bytes.

However, there are errors after that.

The offset is the distance (in bytes) relative to the start of the page.  I.e., logical_address mod page_size.  The bits for this portion of the logical address are not translated (given power of two page size).

The logical (virtual) page number is number of (virtual) page counting from zero.  I.e., $$\frac{logical\_address}{page\_size}$$

As you noted, the physical page is determined by the translation table, indexed using the logical (virtual) address.

Once the physical page number had been found, the physical address of the start of that page is found by multiplying the physical page number by the page size.  The offset is then added to determine the precise physical address.  I.e., $$(physical\_page\_number \times page\_size) + offset$$

So a logical address of, e.g., $508$, with $256$ byte pages would have an offset of
$$508 \mod 256 = 252$$
The logical/virtual page number would be
$$\frac{508}{256} = 1$$
With the given translation table, logical page $1$ translates to the physical page number $2$.  The physical address would then be
$$physical\_page\_number \times page\_size + offset = 2 \times 256 + 252 = 764$$


Find a minimum-weight perfect 2-matching How would one find a minimum-weight perfect 2-matching of a general graph? Is it possible to use standard matching techniques like Blossom V?

A minimum-weight perfect 2-matching of a graph G is a subgraph M of minimal total edge weight, such that each vertex in G is incident by exactly 2 edges from M.

From an answer to my other question it turns out that one can convert this problem to standard matching.

Find a minimum-weight perfect b-matching, where b is even

I still wonder whether this would give the most efficient approach?


For regular languages A and B, determine whether B might match early in (A B) I have two regular languages A and B, and I want to determine whether there is any pair of strings, a in A and b in B, such that (a b) is a prefix of a string in (A B) and the left-most match of B in (a b) includes one or more characters from a.

Raphael's formulation is good:

  Given two regular language A, B, is there a (non-empty) prefix of a word b in B that is a suffix of a word in A so that the rest of b is a prefix of another word in B?

Example

For example, let's say I have two regular languages, one which describes some properly escaped HTML text, and one which describes an end tag:

A := ([^&<>] | [&] [a-z] [a-z0-9]+ [;])*;
B := "</title";

By inspection, I can tell that there is no string (a b) in (A B) such that the first match of B includes characters from a because "<" is a prefix of B which cannot occur as a suffix of A.

But given a different grammar:

A' := (A | "<![CDATA[" ("]"? ">" | "]"* [^\]>])* "]]>")*;
B' := "</title" ([^>\"] | [\"] [^\"]* [\"])* ">";

then there are strings

a = '<![CDATA[</title "]]>"';
b = '</title>';

where (A B) matches '<![CDATA[</title "]]>"</title>' and the left-most match of B is '</title "]]>"</title>' which includes a non-empty suffix of a : '</title "]]>"'.

Motivation

A in my situation describes the output of an encoder/sanitizer that is derived from a grammar, so an untrusted input is fed to the encoder/sanitizer and I know the output matches A by construction.

B is a limit condition in a larger grammar that describes how parsers determine where a chunk of an embedded language ends so they can hand it off to a parser for the embedded language.

My end goal is to be able to determine when I can optimize away runtime checks that ensure that it is safe to embed a particular encoded string.  For these examples, it would be safe to optimize out the first check, but not the second.

Is this a solved problem?  Does it have a name?  Any pointers appreciated.

If I translate your description properly, here is what you want to ask:

  Given two regular language $A$, $B$, is there a prefix of a word $b$ in $B$ that is a suffix of a word in $A$ so that the rest of $b$ is a prefix of another word in $B$?

Formally:

  Given regular $A$ and $B$, are there $a = wx \in A$ and $b = yz \in B$ so that $xy \in B$?

Deciding this boils down to deciding whether

$\qquad B \cap (\operatorname{suff}(A) \cdot \operatorname{pref}(B) ) = \emptyset$.

Now we employ some closure properties: $\mathrm{REG}$ is closed against right and left quotient, concatenation and intersection, so with

$\qquad \operatorname{suff}(A) = A \backslash \Sigma^*$ and
$\operatorname{pref}(B) = B / \Sigma^*$

the set we want to check for emptiness is regular, and therefore the check is indeed decidable.

In order to actually do this, I suggest you build automata for $\operatorname{suff}(A)$ and $\operatorname{pref}(B)$, concatenate them, intersect the result with the automaton for $B$ and use the standard check for emptiness (is a final state reachable from the initial state?).

Note that you never need DFA, all of this works nicely with NFA. Therefore, no exponential state explosion occurs; intersection multiplies the state numbers, though.


Does NP = coNP imply the collapse of PH to level 1? It was already asked here whether NP=coNP implies P=NP. I'd like to approach that question from the perspective of the Polynomial-Time Hierarchy.

Here is a theorem from Oded Goldreich's "Computational Complexity" (Proposition 3.10):

  For every $k \ge 1$, if $\Sigma_k = \Pi_k$ then $\Sigma_k =
 \Sigma_{k+1}$, which in turn implies $PH = \Sigma_k$.

Now, since $\Sigma_1=NP$ and $\Pi_1 = coNP$, doesn't it imply that $PH = \Sigma_1$, which ultimately implies $P = NP$?

No.  $PH=NP$ doesn't imply $P=NP$, because $PH$ is not the same class as $P$.

Roughly speaking, $PH$ includes $P$, $NP$, $coNP$, and more: $PH$ includes $\Sigma_i$ and $\Pi_i$ for all $i$.  Formally, $PH$ is defined as

$$PH = \Sigma_0 \cup \Pi_0 \cup \Sigma_1 \cup \Pi_1 \cup \Sigma_2 \cup \Pi_2 \cup \cdots.$$

If $NP=coNP$, then we have $\Sigma_1=\Pi_1$, and by Proposition 3.10, we have $\Sigma_1=\Sigma_2=\Sigma_3 =\cdots=NP$ and $\Pi_1=\Pi_2=\Pi_3=\cdots=coNP=NP$, so

$$\begin{align*}
PH &= \Sigma_0 \cup \Pi_0 \cup \Sigma_1 \cup \Pi_1 \cup \Sigma_2 \cup \Pi_2 \cup \cdots\\
&= P \cup P \cup NP \cup NP \cup NP \cup NP \cup \cdots\\
&= NP.
\end{align*}$$


Algorithm to test whether a language is context-free Is there an algorithm/systematic procedure to test whether a language is context-free?

In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in \mathbb{N}\}$), test whether the language is context-free or not.  Imagine we are writing a web service to help students with all their homeworks; you specify the language, and the web service outputs "context-free" or "not context-free".  Is there any good approach to automating this?

There are of course techniques for manual proof, such as the pumping lemma, Ogden's lemma, Parikh's lemma, the Interchange lemma, and more here.  However, they each require manual insight at some point, so it's not clear how to turn any of them into something algorithmic.

I see Kaveh has written elsewhere that the set of non-context-free languages is not recursively enumerable, so it seems there is no hope for any algorithm to work on all possible languages.  Therefore, I suppose the web service would need to be able to output "context-free", "not context-free", or "I can't tell".  Is there any algorithm that would often be able to provide an answer other than "I can't tell", on many of the languages one is likely to see in textbooks?  How would you build such a web service?

To make this question well-posed, we need to decide how the user will specify  the language.  I'm open to suggestions, but I'm thinking something like this:

$$L = \{E : S\}$$

where $E$ is a word-expressions and $S$ is a system of linear inequalities over the length-variables, with the following definitions:

Each of $x,y,z,\dots$ is a word-expression.  (These represent variables that can hold any word in $\Sigma^*$.)
Each of $a,b,c,\dots$ is a word-expression.  (Implicitly, $\Sigma=\{a,b,c,\dots\}$, so $a,b,c,\dots$ represent a single symbol in the underlying alphabet.)
Each of $a^\eta,b^\eta,c^\eta,\dots$ is a word-expression, if $\eta$ is a length-variable.
The concatenation of word-expressions is a word-expression.
Each of $m,n,p,q,\dots$ is a length-variable.  (These represent variables that can hold any natural number.)
Each of $|x|,|y|,|z|,\dots$ is a length-variable.  (These represent the length of a corresponding word.)

This seems broad enough to handle many of the cases we see in textbook exercises.  Of course, you can substitute any other textual method of specifying a language in algebraic form, if you like.

By Rice's theorem, to see if the language accepted by a Turing machine has any non-trivial property (here: being context free) is not decidable. So you would have to restrict the power of your recognizing machinery (or description) to make it not Turing complete to hope for an answer.

For some language descriptions the answer is trivial: If it is by regular expressions, it is regular, thus context free. If it is by context free grammars, ditto.


Solving a simple recurrence I'm having a real hard time solving recurrences using the substitution method.

Show that: $T(n) = T(n/2) + 1$ is $O(\lg n)$

I thought this to be relatively easy:

We have to show that $T(n) \leq c \lg n$

Substitution gives me:

$\qquad
  \begin{align}
    T(n) &\leq c \lg(n/2) + 1 \\
         &= c \lg n - c \lg 2 + 1 \\
         &= c \lg n - c + 1 \\
         &\leq  c \lg n
\end{align}$

for every c.

I was under the impression this was it, but when I was looking for an answer, I came around a much more elaborate answer on the web, given  involving subtracting a constant. I don't get why that's needed, I thought I had shown what was needed.

Any help would be greatly appreciate, starting Monday I'm enrolled in an algorithms class and I don't want to get behind!

We are using the CLRS book (surprise) and though I appreciate the amount of information in it, I'd rather have some more resources. I've really enjoyed a datastructures class and I really think I can enjoy this as well, but more resources would be very much appreciated.

Luckily i had 2 day ago the algorithm exam and so i was able to solve your question :-)
When solving recurrences try first to use the Master method, if you can't succeed than try other methods.


Can an NFA have multiple accepting states? I am currently preparing for exam. While studying Finite Automata, i got confused. I know a DFA can have multiple accepting states, but can an NFA also have multiple accepting states?

Whenever one is in doubt about central notions, one must consult the definitions of them. You should do this yourself (I assume that you have a textbook at your disposal).

Below is Definition 1.37 from Introduction to the Theory of Computation by Michael Sipser:

A nondeterministic finite automaton is a 5-tuple $(Q,\Sigma,\Delta,q_0,F)$, where

$Q$ is a finite set of states,
$\Sigma$ is a finite alphabet,
$\delta: Q \times \Sigma_{\epsilon} \rightarrow \mathcal{P}(Q)$ is
the transition function,
$q_0 \in Q$ is the start state, and
$F \subseteq Q$ is the set of accept states.

Item 5 tells us that $F$ is just a set of states, which means that it can be the empty set, a singleton set or a set with several states as elements.


Programming language semantics prototyping tool Is there any tool for prototyping a programming language semantics and type system and that also allows for some sort of model checking of standard properties, like type soundness?

I'm asking this, because I'm reading a book on Alloy and it provides the exact functionality that I want, but for models expressed using relational logic.

I'm aware of Ott, but it does not have this sort of "model checking" capability, since it is focused on generating code for proof assistant systems.

Any reference on such tool existence would be nice.

Although there are frameworks created specifically for the purpose of prototyping programming languages (including their semantics, type systems, evaluation, as well as checking properties about them), the best choice depends on your particular case and specific needs.

Having that said, there are multiple (perhaps not so distinct) alternatives you might take (which includie the ones you've already mentioned):

using a specific language/framework designed for creating and prototyping new languages: as an example, Redex [1], a domain-specific language embedded in Racket for specifying and checking (operational) semantics of programming languages, which, given a definition of a language, provides easy handling of tasks such as typesetting (in Latex), inspecting traces of reduction, unit tests and random testing (e.g. for checking typing)
using general modelling languages that offer defining and performing certain analyses easily, as long as they can capture the specific language at hand to the needed extent; Alloy [2] is an example of such an approach: albeit pretty general and flexible, languages can be modelled as relations between states, while the support for model checking (e.g. evaluation within such language) comes for free after the semantics is expressed with a relation model (e.g. some ideas for modelling semantics of a language can be found in [3])
embedding the language to check its properties using a theorem prover; an example would defining the language as well as its semantics by embedding it in a proof system like Coq [4] (more details about this approach, as well as discussion and demonstration of the difference between deep and shallow embedding in Coq is given in [5])
using Ott (as already mentioned, with similar in spirit as Redex, but providing a new definition language rather than being embedded); Ott allows you to define the programming language in a convenient notation, and produce typesetting and definitions in a proof system (usually with deep embedding), where most of the checking (i.e. proof) needs to be performed manually
developing the language and its semantics, as well as appropriate checks (e.g. as tests) "from scratch" in a general-purpose programming language and translation into other systems if need be, for checking purposes (some languages, like Leon [6], include built-in verifiers, which allow automatically proving certain properties and make this approach similar to embedding in a proof system)

Note that there is the trade-off between how easy is to use the framework/tool (e.g. as easy as laying out the definition on paper or in Latex) and how powerful the mechanisms for checking the properties about the language are (e.g. embedding the language in a theorem prover can allow checking very elaborate properties).

[1] Casey Klein, John Clements, Christos Dimoulas, Carl Eastlund, Matthias Felleisen, Matthew Flatt, Jay A. McCarthy, Jon Rafkind, Sam Tobin-Hochstadt, and Robert Bruce Findler. Run Your Research: On the Effectiveness of Lightweight Mechanization. POPL, 2012.

[2] Daniel Jackson. Alloy: a lightweight object modelling notation. TOSEM, 2002.

[3] Greg Dennis, Felix Chang, Daniel Jackson. Modular Verification of Code with SAT. ISSTA, 2006

[4] Coq formal proof management system

[5] Formal Reasoning About Programs. Adam Chlipala, 2016

[6] Leon automated system for verifying, repairing, and synthesizing functional Scala programs


How to prove the equivalence between Hoare and Floyd assignment axioms? How to show that these two axioms are equivalent:

1: $\{G[v/e]\} v:=e \{G\}$

2: $\{F\} v:=e \{\exists v' (F[v/v'] \land v=e[v/v'])\}$

I've tried with $G = \exists v' (F[v/v'] \land v=e[v/v']) $and then I get $G[v/e] = F$, but when I try $F = G[v/e]$ then from $\exists v' (F[v/v'] \land v=e[v/v'])$ I can't obtain $G$.

Is that even correct way to approach this proof?

Thanks!

p.s. There was a question already, but isn't answered: How to show equivalence of the Hoare assignment axiom vs Floyd assignment axiom?

but when I try $F = G[v/e]$ then from $\exists v' (F[v/v'] \land v=e[v/v'])$ I can't obtain $G$.

We can assume $v'$ not free in $G$. Then, we have

$$
\begin{array}{ll}
& \exists v' (F[v/v'] \land v=e[v/v']) \\
\iff & \mbox{\{def. $F$\}}\\
& \exists v' (G[v/e][v/v'] \land v=e[v/v']) \\
\iff & \mbox{\{property of $H[v/-][v/-]$\}}\\
& \exists v' (G[v/(e[v/v'])] \land v=e[v/v']) \\
\iff & \mbox{\{replacing equals with equals\}}\\
& \exists v' (G[v/v] \land v=e[v/v']) \\
\iff & \mbox{\{$[v/v]$ has no effect\}}\\
& \exists v' (G \land v=e[v/v']) \\
\iff & \mbox{\{$v'$ not free in $G$\}}\\
& G \land \exists v' (v=e[v/v']) \\
\implies & \mbox{\{logic\}}\\
& G
\end{array}
$$

The crucial step is to realize that any $v$ which occurs free in $G[v/e]$ is a $v$ that originated from $e$. Hence, $G[v/e][v/t] = G[v/(e[v/t])]$.

Also note that we don't get exactly $G$ but a slightly stronger postcondition. Since postconditions can be weakened, this is not an issue.


Is there any uncountable Turing decidable language? There are many(and I mean many) countable languages which are Turing-decidable. Can any uncountable language be Turing decidable?

Every language over a finite (or even countable) alphabet is countable. Assuming your Turing machine alphabet is finite, any language it can possibly accept is countable.


Prove that the class of CFG languages that are closed under reversal is undecidable Note

The wording of the title may be a bit vague, but I'm not asking if CFLs are closed under reversal. Please see below.

Problem Description

Given a word $w$, define $w^{r}$ to be its reversal.

Let $L=\{ G \vert G \text{ is a } CFG \text{ and for every } w \in L(G), w^{r} \in L(G) \}$

Prove that $L$ is undecidable.

My Attempt

I am aware that I should reduce a known-to-be-undecidable language to L, but by looking at the four undecidable languages here (Equivalence, Disjointness, Containment, Universality), I still failed to determine which language I can use. Please guide me a direction, thank you.

Let $G_1,G_2$ be two context-free grammars. We can construct a context-free grammar $G$ such that
$$
L(G) = \#L(G_1) \cup L(G_2)^r\#,
$$
where $\#$ is a new symbol. The language $L(G)$ is closed under reverse iff $L(G_1) = L(G_2)$.


Seek to infer "correct" route from sequence of stops Let us consider school buses. Let a 'Bus Route' be a sequence of bus stops travelled by a single school bus (day after day). Let a 'Bus Stop' be a combination of Latitude (Lat), Longitude (Lon) and Time-of-Day (ToD). That is, a bus may stop at the same Lat/Lon to pick up kids in the morning and again in the afternoon to drop them off. Furthermore, a bus may stop at a certain Lat/Lon at 7am to pick up high school kids, drop them at school, and then visit the same Lat/Lon at 7:30am to pick up middle school kids, and again at 8am to pick up elementary school kids.

Suppose that a bus sends its Lat/Lon/ToD every time it activates its stop-arm (which it does when it stops to let kids on/off the bus). Suppose we have the Lat/Lon/ToD information for a particular bus for 20 consecutive days.

In a perfect world the bus would make every stop at approximately the same time every day. In the imperfect world in which we live these things happen:

When there are no kids waiting at a bus stop in the morning the driver does not stop (so no Lat/Lon/Tod get sent). On any given day there may or may not be kids at any given bus stop.

When no kid are waiting to get off the bus a given stop the bus will not stop (so no Lat/Lon/Tod gets sent).

So, if there are "in fact" 30 stops, on some days the bus will make 30 stops, on other days it may make 20 stops, etc.

Let's assume that algorithms are already in place to analyze the Lat/Lon/ToD tuples for the 20 days worth of data and correctly identify a set of Bus Stops.

Placing the Bus Stops into the correct order would be a simple matter except that:

On some days the bus may visit stops in one order and some days in a different order. So, if Bus Stops are labelled with letters, on one day the path might be:
A C D F H I J L N

and on the next day the order might be:

A B C D H F J L M N

(Notice there is a sequence "D F H" in the first and "D H F" in the second) This can happen for several reason, including:

a) different drivers have different ideas about what is the best route.
b) the driver made a mistake, missed a stop, and has to go back.

ASSUME: there is nobody to ask, "What is the correct route (sequence of stops)?"

PROBLEM: using only the collected data, how can we construct the sequence "most likely" to be correct?

To be clear, this is not an optimization problem; I do not seed to find the "best" route. Rather, if, for example, the bus made exactly the same sequence of stops on 19 of 20 days and on the one odd day the order of two stops was reversed (compared to the other 19) then the "correct" route would be the sequence traveled on the 19 days. What I seek to do is to infer what is most likely the intended route by analyzing when and where the bus actually stops given that drivers skip some stops on some days and sometimes visit some days in different sequence on different days

Thanks for any help you can offer.

Regards, Matt

To be clear, this is not an optimization problem; I do not seed to find the "best" route.

Actually this is an optimization problem!  Just instead of optimizing for shortest length or fastest time, you're optimizing for highest likelihood:

  What I seek to do is to infer what is most likely the intended route
   [...]

Now you just have to figure out your model for likelihood.

For example, say that the bus drives$$
\left[\mathrm{A}\right]{\rightarrow}\left[\mathrm{B}\right]{\rightarrow}\left[\mathrm{C}\right]
$$half the time, then$$
\left[\mathrm{A}\right]{\rightarrow}\left[\mathrm{C}\right]{\rightarrow}\left[\mathrm{B}\right]
$$the other half of the time.  But, it tends to do the first route on odd-numbered days, unless it's raining.  Except, the driver "Bob" reverses this pattern, whereas "Suzzy" always does the first one and "Atomic Robot #7" always does the second one.  What do you infer from that?

Math has no opinion on this topic.  For example, if you choose to believe that whatever "Bob" does is always correct, even if every other driver disagrees with him, that's your belief; math doesn't object.

So, what you need to do is construct a model for assessing how likely you believe a particular solution is given a set of data, then optimize for likelihood given the data.


What is it called when f(g(x)) = x? There are a couple of function pairs which give the identity when composed, e.g.,

decrypt(encrypt(value)) == value
deserialize(serialize(data, filepath)) == data

What is this property called? Suppose one function undoes the property of the other, and it is guaranteed that this is possible for all values (within the domain of interest).

I would add to the existing answer that the composition $h = f \circ g$ is the identity, which you already pointed out. This means that $g$ is the right-inverse of $f$, and $f$ is the left-inverse of $g$. That makes each of $f$ and $g$ invertible on the given side. For the pairs you have given, I would expect $g \circ f$ to also be the identity in the naïve/straightforward case, and so the left/rightness is flipped, and you have full inversion. The domain matters, as usual.
As pointed out in the comments, this is not necessarily the case for some kinds of the functions you give—re-encrypting after retrieving the original value $(g \circ f \circ g)(x)$ may not necessarily give the same encrypted code $g(x)$; but then, it’s not nearly useful to consider $g$ a function, for the normal rules don’t apply. Notice that we still take the value passed to $f$ (here, the decryptor) to be an encrypted value; we assume the domain of $f$ to be properly encrypted values. Mathematically we are unable to apply $f$ to anything else (though I could have used a name like $y = g(x)$). Programmatically, of course, the type system may permit values outside the domain to be given, and then we either get an error or garbage. Again, I consider those irrelevant and outside the domain here.
Versioned serialization actually doesn’t have this issue—a function that deserializes or serializes a different version than $f$ or $g$ is not $f$ or $g$, respectively, and therefore not relevant! The domain matters.
We also have $\forall x$ in the domain $h(x) = x$ by definition, and that means every $x$ is a fix-point of $h$ (this is trivially true for any identity).


Proving greedy choice property of fractional knapsack A typical way of proving the greedy choice property of the fractional knapsack problem is as follows:

From Slide 5 of this link:

Given: A set of items $I = \{I_1,I_2..I_n\}$ with weights $\{w_1,w_2 ... w_n\}$ and values $\{v_1,v_2 ...v_n\}$. Let $P$ be the problem of selecting items from $I$, with the weight limit $K$ such that the resulting value is maximum.

Let $O = \{o_1,o_2 ... o_j\} \subseteq I$ be the optimum solution of problem $P$.

Let $G = \{g_1,g_2 ... g_k\} \subseteq I$ be the greedy solution, where the  items are ordered according to the greedy choices.

We need to show that there exists some optimal solution $O'$ that includes the choice $g_1$
.

CASE 1: $g_1$ is non-fractional.

If $g_1$ is included in $O$, then we are done.
If $g_1$ is not included in $O$, then we arbitrarily remove $w_{g_1}$ worth of stuff from $O$ and replace it with $g_1$ to produce $O'$.
$O'$ is a solution, and it is at least as good as $O$.

In the above proof, step $3$ for CASE 1 merely shows that weight criteria is satisfied. How does it show that $O'$ is also an optimal solution(i.e. in terms of value achieved), more so when we are "arbitrarily removing $w_{g_1}$ worth of stuff" without paying attention to corresponding change in value ?

UPDATE: I found the answer in terms of change in value here. I am not sure if this should go into the answer part. Mods, please suggest.

Remember that $O$ is assumed to be an optimal solution.
If $O'$ is a solution that is at least as good as $O$, then $O'$ has to be optimal too.

In particular, since $O$ is optimal, $O'$ cannot be better than $O$; so $O'$ must be exactly as good as $O$.  Since there's nothing better than $O$, and since $O$ and $O'$ have the same goodness, there can't be anything better than $O'$ either.  Consequently, $O'$ is also optimal: both $O$ and $O'$ are optimal solutions.  (There can be more than one optimal solution.)


Maximum bipartite matching with extra reward for covering certain sets Consider the following variation of Bipartite Maximum Matching.  As usual, we have a bipartite graph $G$.  In addition, there is an  additional collection of sets $S_1,S_2,\dots,S_k$, with each set $S_{i}$ being defined as a collection of nodes from the right side of the  graph $G$ as well as a weight.

Suppose that in a matching all nodes which $S_{i}$ describes are matched. Then an extra bonus of weight($S_{i}$) is gained.

Given a certain matching, define as $Y$ the set of all indexes $i$ such that  $S_{i}$ is fully covered by the matching (i.e all its nodes are matched).  Then the profit of this matching is

$$\text{# edges} + \sum_{a \in  Y} \text{weight}(S_{a}),$$

where $\text{# edges}$ is the number of edges in the matching.

The problem is, of course, to find the matching which maximizes the above quantity.

I instantly thought of the following exponential time algorithm.  The algorithm works as follows:

For i in [0,2^k -1]:
    Define X= a subset containing all S_{j} such that  j-bit in i is 1.
    Try to find a maximum matching  only for the nodes which are defined by the elements of X
    If it is a maximum matching(I.e all elements in the right side are matched)
       Add all the other nodes not already present and continue the augmenting path algorihtm
Pick the maximum for all i

As I remember from my algorithm class, in the augmenting path algorithm, once a node in the left side has been  assigned to the matching it  never leaves it. Hence, the algorithm  tries to make sure that in each iteration  certain  sets will be satisfied. Essentially, it is  brute force. Therefore, optimality is proven easily. Unless of course my assumption is wrong.

The running time is $O(2^{k}\text{poly}(V,E))$ which is fine for my needs as $k$ is only 7.

But  I am wondering whether there exists a  polynomial algorithm for this or if the problem is NP-hard. Its clearly in NP but I have not had much success proving NP-completeness.

Let Y131P be "your problem with [weights all equal to 1] and

[left-side degrees bounded above by 3] and [right-side degrees all equal to 1]".

I will show hardness of Y131P.

Wikipedia gives two local gadget reductions from 3-SAT to 1-in-at-most-3-SAT.

The longer one induces a locally-computable bijection between

satisfying assignments whose inverse is also locally-computable.

The following is a linear reduction from 1-in-at-most-3-SAT to Y131P:

There is a left-side node for each variable and for each clause.    Each literal corresponds

to a set of  ( 1 + number_of_occurences_of_that_literal_in_the_input )  right-side nodes,

one of which is labeled with the literal LIT and the others of which are labeled  $\langle$LIT,C$\rangle$  for the

constraints C in which they appear.    Each right-side node labeled with a literal is adjacent

to the left-side node labeled with that literal's variable, and each right-side node labeled

with a pair  $\langle$LIT,C$\rangle$  is adjacent to the left-side node that corresponds to the constraint C.

(A satisfying assignment induces a matching which uses every left-side node and number_of_variables sets, so its value is    # left-side edges  +  number of variables    .

Since the graph is bipartite, no matching can have more edges than the number of left-side nodes.

Due to the left-side variables, sets for complementary literals can't simultaneously be chosen.  Thus, no matchings have value greater than    # left-side edges  +  number of variables  ,

and since the constraints are Exactly-1, there is an efficiently-computable bijection

[between [matchings whose value is that sum] and satisfying assignments]

whose inverse is also efficiently computable.)

In particular, Y131P is FNP-hard.

By [that reduction being linear] and the sparsification lemma, one gets that a

strong version of ETH would imply that Y131P takes takes 2Ω(|E|) time to decide.

Since Y131P can be efficiently padded without changing k (just throw in

isolated edges between new vertices), the same strengthened ETH assumption

would imply that Y131P algorithms' runtime's dependency on k must be 2Ω(k).

The rest of this answer's results apply even when the weights are

given in unary and are equal to each other (but not necessarily to 1).

As I'll use the phrase, "threshold constraints" specify [a multi-set of literals] and

[a positive integer (the "threshold") that's at most the constraint's "size"], where its "size"

is the sum of the multiplicities of the literals in the multi-set.  The constraint is satisfied

if and only if the sum of the multiplicities of the true literals is at least the threshold.

The following is a reduction from [satisfying a list of threshold constraints] to

your problem such that [the number of sets is twice the number of variables] and

[the degree of the left-side nodes are at most  max ( 2 , size_of_largest_constraint ) ]

and the degree of each right-side node is at most

max  (  1  ,  [the maximum, taken over the constraints, of size minus threshold]  )    :

Each variable corresponds to one left-side node and each constraint corresponds

to  ( size_of_the_constraint - the_constraint's_threshold )  left-side nodes.

Each literal corresponds to a set of

( 1 + number_of_occurences_of_its_complement_in_the_input )

right-side nodes, one of which is labeled with the literal LIT and the others of which

are labeled  $\langle$LIT,C$\rangle$  for each occurrence of LIT's complement in a constraint C.

For each constraint C, for each literal LIT whose complement is in C, the node labeled

$\langle$LIT,C$\rangle$  is adjacent to [the left-side nodes that correspond to C] and nothing else.

For each variable v, [the 2 right-side nodes labeled with v's literals] are

adjacent to [the left-side node that corresponds to v] and nothing else.

The weights are equal to each other and greater than the number of variables plus

[the sum, taken over the variables, of the maximum, taken over the variable's

positive and negative literal, of the number of occurrences of that literal in the input].

(Due the the left-side variables, one can't choose both a variable and its negation.

Due to the number of nodes corresponding to a given constraint, one can't

choose too many literals in that constraint to be false, but can do anything else.

The weights are equal and large-enough to dominate over the other part of the matchings' values.

Thus, there's a many-one correspondence between [solutions to the outputted instance of your problem] and [solutions to the input problem], although the output problem can easily have

more than one solution even when the constraint satisfaction problem has a unique solution.)

Since threshold constraints can implement clauses by letting the thresholds be 1,

it follows that if $\big[$there is a real number c such that  c < 1/2  and there are arbitrarily-large

integers d such that for all integers b, there is an algorithm for [$\hspace{.02 in}$your problem with [$\hspace{.02 in}$left-side nodes

having degree d$\hspace{.02 in}$] and [right-side nodes having degree d-1] and  |E| < b$\cdot \hspace{-0.02 in}$k ]  whose runtime is

not eventually bounded below by  2$\hspace{.02 in}$c$\hspace{.02 in}\cdot \hspace{-0.02 in}$k $\big]$   then the corresponding strengthing of SETH is false.

For the same reason, high-power compression of the graph and/or the sets

would yield compression of [threshold-constraint]-SAT, and I'm

not aware of any feasibility results regarding such compression.

(Reminder:  Threshold constraints can implement clauses by letting the thresholds be 1.)

However, that does not say anything about compressing the weights, and independently:

Weighted set packing reduces to maximum-weight independent set with number of vertices equal to the number of sets (adjacent if and only if intersect).  Maximum-weight independent set reduces to your problem (incidence graph).  When the right-side nodes each have degree at most 1, your problem reduces to weighted set packing with the number of sets equal to the number of vertices.

(Remove sets with degree-zero nodes, remove sets with a pair of nodes adjacent to the same node, then replace each set with the set of left-side nodes adjacent to an element of the set

and weight those sets by the original sets' weight plus number of non-removed elements.)

Thus, when the right-side nodes each have degree at most 1, your problem can be

somewhat kernelized.  (That "somewhat kernelization" doesn't simplify the weights.)


Prove, a^2+b^2=c^2,there exists only 1 case such that a,b,c are consecutive non negative integers(3,4,5) I want to prove, $a^2+b^2=c^2$,there exists only 1 case such that a,b,c are consecutive non-negative integers(3,4,5).

I have no clue to prove this lemma. Please help me to prove this lemma.

$n^2 + (n + 1)^2 = (n + 2)^2 \Rightarrow n^2 + n^2 + 2n + 1 = n^2 + 4n + 4 \Rightarrow 2n^2 2n + 1 = n^2 + 4n + 4 \Rightarrow n^2 - 2n - 3 = 0 \Rightarrow n = -1, 3$

Therefore, 3 is the only plausible solution.


How can Machine Learning be used to find attributes/characteristics of graphs? I am aware ML is not necessary for many graph classification problems (as the graph theorists have many clever solutions), but I'm specifically interested in ML approaches to these types of questions. I imagine if you had enough training examples (1000s?) you could use a supervised approach for classification type of questions. I also assume an adjacency matrix would be a good data representation to use for ML approaches to undirected graph classification. Example problems are shown below.

1.) Given an undirected graph represented by an adjacency matrix, broadly speaking, how (if possible) could machine learning be used to find if said graph has a hamiltonian path?

2.) Given an undirected graph represented by an adjacency matrix, how can ML be used to determine if the graph is a tree?

ML is not likely to be a good approach for these kinds of problems.  It will probably perform far worse than a hand-designed algorithm.  Current ML is not magic; it is just a form of pattern-matching.


A simple question on #P Wiki (http://en.wikipedia.org/wiki/Sharp-P) says 'In computational complexity theory, the complexity class #P (pronounced "number P" or, sometimes "sharp P" or "hash P") is the set of the counting problems associated with the decision problems in the set NP'.

Is there a counting version for CoNP problems?

Expanding on Timot's comment, $\# P$ consists of all functions which can be expressed as the number of accepting computations of some non-deterministic Turing machine running in polynomial time. It is also the class of all functions which can be expressed at the number of non-accepting computations of some non-deterministic Turing machine running in polynomial time (exercise).

If $f \in \# P$ then $\{ x : f(x) \geq 1 \} \in N\! P$ and $\{x : f(x) = 0 \} \in \mathrm{co}N\! P$; and vice versa, if $L \in N\!P$ ($L \in \mathrm{co}N\!P$) then it can be expressed in the form $\{ x : f(x) \geq 1 \}$ ($\{ x : f(x) = 0 \}$) for some $f \in \# P$.


Why is $L = \{ \langle M \rangle : L(M) = \{ \langle M \rangle \} \}$ not Turing-recognizable? In other words, $L$ is the language of Turing machines that recognize the language consisting of only themselves.

Why is $L$ not Turing-recognizable? $L$ is clearly not decidable by Rice's Theorem, but how do I go one step further and also prove that no machine can enumerate $L$?

Given a Turing machine $T$, use the recursion theorem to construct a Turing machine $T'$ that halts if its input $x$ is $\langle T' \rangle$, runs $T$ on $x$ if $x < \langle T' \rangle$, and runs $T$ on $x-1$ if $x > \langle T' \rangle$. If you could recursively enumerate $L$, then you could use this reduction to recursively enumerate all machines that never halt.


Converting DFA to RE with Arden's Rule So I've searched around and found the algorithm to do so: How to convert finite automata to regular expressions? and I decided to test out the second-level response, Raphaels, and while I was getting correct regexes at least to my knowledge, I was having some weird issues with variables/state names. Please help me understand what my mistake is here in my process:

Consider the DFA that is governed by these equations and $\Sigma = \{a, b\}$:
$$Q_0 = bQ_2 \cup aQ_1
\\ Q_1 = bQ_2 \cup aQ_0
\\ Q_2 = aQ_2 \cup bQ_2 \cup \varepsilon$$

I'm sorry I don't have a picture of the graph, but I think this should be fairly simple to visualize. It is an unminimized DFA that pretty much accepts every string with at least 1 'b', as it bounces back and forth from $Q_1$ and $Q_0$ every time an 'a' is reached, both $Q_1$ and $Q_0$ have edges to $Q_2$ from 'b', and $Q_2$ is an accept state that stays at $Q_2$ no matter what character it sees. Now I attempt to do the reduction method we see in Raphael's post:

$Q_1 = bQ_2 \cup a(bQ_2 \cup aQ_1)
\\ Q_1 = bQ_2 \cup abQ_2 \cup aaQ_1
\\ Q_1 = (b \cup ab)Q_2 \cup aaQ_1
\\ Q_1 = (aa)^*(b \cup ab)Q_2$

$\\ Q_2 = a^*bQ_2 \cup \varepsilon
\\ Q_2 = a^*b^* \cup \varepsilon
\\ Q_2 = (a^*b^*)^*$

$\\ \\ Q_1 = (aa)^*(b \cup ab)(a^*b^*)^*$

Now I have two questions here:

Notice that at the end of my $Q_1$ manipulation I moved $(aa)^*$ to the front. This is something that I did out of common sense since thinking about the DFA, $(aa)^*$ has to be first since $Q_2$ doesn't have any outbound edges. Is there a way to formalize what I'm thinking/doing here?
Notice that at the end I have my valid regex equal to $Q_1$. That doesn't seem right, since we want to find the regex associated with $Q_2$! But a quick simulation through my head tells me that it actually is the regex associated with $Q_2$. So what is going on?!

Thanks so much for your help.

Your manipulation where you went from $Q_1 = (b \cup ab)Q_2 \cup aaQ_1$ to $Q_1 = (aa)^*(b \cup ab)Q_2$ was not valid.  Instead, in this case I suggest that you first start by finding a nice form for $Q_2$, before trying to manipulate $Q_1$.

A good way to handle $Q_2$ is to note that $Q_2 = a Q_2 \cup b Q_2 \cup \epsilon$ implies $Q_2 = (a \cup b) Q_2 \cup \epsilon$ (by the distribute law); when then apply Arden's rule to conclude that $Q_2 = (a \cup b)^* \epsilon = (a \cup b)^*$.

Now plug in this expression for $Q_2$ into your equations for $Q_0$ and $Q_2$.  You obtain

$$\begin{align*}
Q_0 &= b (a \cup b)^* \cup a Q_1\\
Q_1 &= b (a \cup b)^* \cup a Q_0
\end{align*}$$

Next, take the expression for $Q_1$ and plug it into the first equation.  We see that

$$Q_0 = b (a \cup b)^* \cup a b (a \cup b)^* \cup a a Q_0.$$

Now applying Arden's rule tells us that

$$Q_0 = (aa)^* (b \cup ab) (a \cup b)^*.$$

That's the regular expression that you ultimately wanted.


How do I sort these elements in O(n) time? So let's say I have an array of elements where each of the values can range from 0 to $n^2-1$. I'm trying to make an algorithm to sort this array in O(n) running time and I was thinking of using radix sort. The run time of radix sort is O(d(n+N)) or O(dn) if n is really large. So how can I modify radix sort so that it runs in O(n)?

EDIT:
I don't think you guys understand this. The amount of elements in the array is n but the ACTUAL value for each element can range from 0 to n^2 - 1. So if we have an array with 10 elements in it then the largest the element can be is 99 and the smallest it can be is 0 but there will still be 10 elements in the array.

If you want to implement this on a RAM with integer math (ie. a real computer if your n is smaller than $2^{32}$), you can have a look at Upper bounds for sorting integers on random access machines. The authors show that integers in the range [0,$n^c$] can be sorted in $O(n(1 + \log c))$. Word RAM models add some loglog factors to that runtime.


Propositional logic and connectives(translating to english) I want to know some stuff about translating compound statements to english:

For the propositions below:

p: You have the flu.
q: You miss the final examination.
r: You pass the course.

I want to know how to translate the following compound proposition to english:

1). p or q or r.

I tried something like this:

You have the flu or you miss the final examination or you pass the course.

I was just wondering about the usage of commas.

2). (p implies not r) or (q implies not r)

I tried something like this:

If you have the flu, then you do not pass the course, or if you miss the final examination, then you do not pass the course.

Again, I was wondering about the comma usage.

Can someone please help?

The first thing to say is that in propositional logic every statement will have a truth value.

If (P or Q or R) evaluates to True (which it doesn't have to) then a natural English way to translate would be:

  Either you have the flu, you miss the final examination or you pass the course.

Note that this "or" is clearly inclusive - meaning that it is possible that more than one of those things happens but at least one must. To make that clear beyond doubt in natural English you might structure the sentence using "at least". This will be much more long winded but avoids the person you are communicating with thinking that you might mean exclusive "or" (e.g. the type of "or" used in "true or false" - it can be one or the other but not both). If you wanted to account for this you might say something like:

  At least one of the following is true: you have the flu, you miss the final examination or you pass the course.

For your second case what you said is not very natural. You would typically hear someone say:

  You won't pass the course if you have the flu or miss the final examination.

If you are supposed, for whatever reason, to structure the answer as you did, the commas should be removed after your "if" clauses. This would be better:

  If you have the flu then you do not pass the course, or if you miss the final examination then you do not pass the course.


Unique path in a directed graph I'm designing an algorithm for a class that will determine if a directed graph is unique with respect to a vertex $v$ such that for any $u \ne v$ there is at most one path from $v$ to $u$. I've started by using BFS (breadth-first search) to find the shortest path from v to another vertex u, and then running BFS again to see if an alternate path can be found from v to u. I think this is too time consuming however. Does anyone have any hints as to how the solution can be found with a shorter execution time?

Use BFS to work backwards from v, flagging each vertex as 'visited' as you go.  If you ever hit a vertex you've previously visited, your graph doesn't have the uniqueness property.  Otherwise, it does.


Online algorithms and changing past decisions We know that for some online problems, algorithms can decrease their competitive ratio greatly if they are allowed to change some of their past decisions (see http://epubs.siam.org/doi/pdf/10.1137/1.9781611973402.35).

I wonder if there are instances of online problems such that the competitive ratio does not decrease even if the algorithm is allowed to change its decisions ?

Every problem where the online algorithm is optimal, i.e. has competitive ratio 1, is a (trivial) example. Such algorithms exist, for example for some scheduling problems.


Why do non regular languages have infinitely many equivalence classes? For example, for the language $L = \{a^nb^m|n \neq m\}$, why does it have infinitely many equivalence classes? How do I show/see that?

There are at least two ways. The first way is to give infinitely many pairwise inequivalent words. In the case of your language, you can take $\{ a^n : n \geq 0 \}$, for example (exercise).

The second way is to prove that the language is not regular. The Myhill–Nerode theorem then implies that it has infinitely many equivalence classes. The reason is that for any language, we can construct a DFA (finite or infinite!) for the language whose states are the equivalence classes. If there are finitely many then this is a bona fide DFA, and we get that the language is regular. Conversely, for every regular language, the states of the minimal DFA correspond to the equivalence classes.


O(·) is not a function, so how can a function be equal to it? I totally understand what big $O$ notation means. My issue is when we say $T(n)=O(f(n))$ , where $T(n)$ is running time of an algorithm on input of size $n$.

I understand semantics of it. But $T(n)$ and $O(f(n))$ are two different things.

$T(n)$ is an exact number, But $O(f(n))$ is not a function that spits out a number, so technically we can't say $T(n)$ equals $O(f(n))$, if one asks you what's the value of $O(f(n))$, what would be your answer? There is no answer.

Strictly speaking, $O(f(n))$ is a set of functions. So the value of $O(f(n))$ is simply the set of all functions that grow asymptotically not faster than $f(n)$. The notation $T(n) = O(f(n))$ is just a conventional way to write that $T(n) \in O(f(n))$.

Note that this also clarifies some caveats of the $O$ notation.
For example, we write that $(1/2) n^2 + n = O(n^2)$, but we never write that $O(n^2)=(1/2)n^2 + n$. To quote Donald Knuth (The Art of Computer Programming, 1.2.11.1):

  The most important consideration is the idea of one-way equalities. [...] If $\alpha(n)$ and $\beta(n)$ are formulas that involve the $O$-notation, then the notation $\alpha(n)=\beta(n)$ means that the set of functions denoted by $\alpha(n)$ is contained in the set denoted by $\beta(n)$.


Pumping lemma for Context-Free Languages I have a question about a specific pumping lemma problem for Context-Free Languages.

Suppose we have the following Language:

  $L = \{a^{i}b^{j}c^{k}d^{l} \mid 0 < i < k \wedge j > l > 0 \}$

Here is my attemp to prove that the language is not context-free:

Assume $L$ is context-free. Let $n>0$ be the pumping length given by the lemma.

Let $z = a^{n}b^{n+1}c^{n+1}d^{n}$, then $z \in L$.

Than according to the lemma, $z$ can be written as $z = uvwxy$ where the following properties hold:

$|vx| \geq 1$
$|vwx| \leq n$
for every $i \geq 0$, $uv^{i}wx^{i}y \in L$.

We have 6 different possibilities for $vwx$:

$vwx = a^{i}$ where $i \leq n$
$vwx = a^{i}{b^j}$ where $i+j \leq n$
$vwx = b^i$ and $i \leq n$
$vwx = b^{i}c^{j}$ and $i+j \leq n$
$vwx = c^{i}$ with $i \leq n$
$vwx = c^{i}d^{j}$ and $i+j \leq n$

Is this right so far? The thing that I'm unsure of is if my different cases for $vwx$ are right.

How do I choose the pumping length for case 2? If I choose $i$ = 2, what if $i$ is zero ? Then I don't have any contradiction.

Thanks in advance

Let me rephrase property 3 of the pumping lemma: for every $l \geq 0$, $uv^lwx^ly \in L$. Now let's consider the seven different cases:

Case 1: $vx = a^i$ where $i > 0$. Choose $l = 2$ to get $a^{n+i} b^{n+1} c^{n+1} d^n \notin L$.

Case 2: $vx = a^ib^j$ where $i,j > 0$. Like case 1 or case 3.

Case 3: $vx = b^i$ where $i > 0$. Choose $l = 0$ to get $a^n b^{n+1-i} c^{n+1} d^n \notin L$.

Case 4: $vx = b^ic^j$ where $i,j > 0$. Like case 3 or case 5.

Case 5: $vx = c^i$ where $i > 0$. Choose $l = 0$ to get $a^n b^{n+1} c^{n+1-i} d^n \notin L$.

Case 6: $vx = c^id^j$ where $i,j > 0$. Like case 5 or case 7.

Case 7: $vx = d^i$ where $i > 0$. Choose $l = 2$ to get $a^n b^{n+1} c^{n+1} d^{n+i} \notin L$.


Enumerating all n-tuples over a finite domain I would like to create an algorithm which takes in an integer n and returns an array whose entries give all n-tuples of nonnegative integers each of which is at most n, so like

A[n][0] = [0,0,0,...,0],
A[n][1] = [1,0,0,...,0], ...,
A[n][n^(n+1)]=[n,n,n,...,n],

that kind of thing.

If n is small, I can manually create n-many for loops to do this, but in general I would like to allow n to be large. Is there an easy workaround? Any help would be appreciated.

Use recursion.  Something like this:

def f(l, k):
    if l==0:
        yield []
    else:
        for i in range(k):
            for L in f(l-1, k):
                yield [i]+L

Here f(l, k) produces all lists of length l all of whose entries are in the range 0..k-1.  The idea is that if you have all lists of length l-1 (the output of f(l-1, k)) you can use that to generate all lists of length l, by using a for-loop.

If you're not familiar with that Python syntax, try this variant:

def f(l, k):
    if l==0:
        return [[]]
    t = []
    for i in range(k):
        for L in f(l-1, k):
            t.append([i]+L)
    return t

Note that [i] is a list containing a single element, i, and + is the list concatenation operator, so [i] + L is a list obtained by prepending the element i to the front of list L.


Prove that different definitions of big-Oh with n>=1 or n>N are equivalent I am coming across two slightly different definitions of big-oh and need to prove that they are equivalent to each other:

Definition 1: f(n) = O(g(n)) if there exists constants c and N such that f(n) ≤ c g(n) for all n > N.

Definition 2: f(n) = O(g(n)) if there exists a constant c such f(n) ≤ c g(n) for all n≥1.

Intuitively I know that if we choose c large enough we can get rid of N like in definition 2. But how to prove that if definition 1 implies definition 2, and vice versa.

Assume g(n)>0 for all values of n (I need to prove this equality when it holds).

Assume definition $1$ holds. Then we have identified a $c$ that works for all but finitely many $n$. For each of the remaining finitely many $n$, we can check if $f(n)< cg(n)$ holds. If it does, then continue on. If it doesn’t, we can always find a $c’$ such that $f(n)<c’g(n)$ holds for that particular $n$. $c’>c$, so this will also hold for all the previously examined $n$. Iterate this through all the finite many $n$ and take the largest value of $c’$. Then definition $2$ holds.

The other direction is really easy. Try to think about it a bit more, because if you think about it in the right way it’ll be obvious.


Decision problem such that any algorithm admits an exponentially faster algorithm In Hromkovič's Algorithmics for Hard Problems (2nd edition) there is this theorem (2.3.3.3, page 117):

  There is a (decidable) decision problem $P$ such that for every algorithm $A$ that solves $P$ there is another algorithm $A'$ that also solves $P$ and additionally fulfills
  $\qquad \forall^\infty n \in \mathbb{N}. \mathrm{Time}_{A'}(n) = \log_2 \mathrm{Time}_A(n)$

$\mathrm{Time}_A(n)$ is the worst-case runtime of $A$ on inputs of size $n$ and $\forall^\infty$ means "for all but finitely many".

A proof is not given and we have no idea how to go about this; it is quite counter-intuitive, actually. How can the theorem be proven?

It seems to be a simple case of Blum's Speedup Theorem:

  Given a Blum complexity measure $(\varphi, \Phi)$ and a total computable function $f$ with two parameters, then there exists a total computable predicate $g$ (a Boolean valued computable function) so that for every program $i$ for $g$, there exists a program $j$ for $g$ so that for almost all $x$
  $$f(x,\Phi_j(x)) \leq \Phi_i(x)$$

Just let the the complexity measure be the time complexity measure (i.e. $\Phi_e(x)$ is the time complexity of the Turing machine with code $e$) and let $f(x,y) = 2^y$.


Analysis of sorting Algorithm with probably wrong comparator? It is an interesting question from an Interview, I failed it.

An array has $n$ different elements $[A_1, A_2, \ldots, A_n]$ (random order).

We have a comparator $C$, but it has a probability p to return correct results.

Now we use $C$ to implement sorting algorithm (any kind, bubble, quick etc..)

After sorting we have $[A_{i_1}, A_{i_2}, \ldots, A_{i_n}]$ (It could be wrong)。

Now given a number $m$ ($m < n$), the question is as follows:

What is Expectation of size $S$ of Intersection between $\{A_1, A_2, \ldots, A_m \}$ and $\{A_{i_1}, A_{i_2}, \ldots, A_{i_m} \}$, in other words, what is $E[S]$?
Any relationship among $m$, $n$ and $p$ ?
If we use different sorting algorithm, how will $E[S]$ change?

My idea is as follows:

When $m=n$, $E[S] = n$, surely
When $m=n-1$, $E[S] = n-1+P(A_n \text{ in } A_{i_n})$

I dont know how to complete the answer but I thought it could be solved through induction.. Any simulation methods would also be fine I think.

The question seems ill-defined. A faulty/probabilistic comparator will have a radically different impact on different sort algorithms. Each algorithm will have a different, and potentially very complex, analysis.

One possibly interesting note is that you will get exactly reverse sort order when p=0. When p=0.5 the result will be unbiased on ascending vs descending, but the resulting permutations will not be equally likely.


Is co-P recursively enumerable? P is RE, but is the complement of the class of languages decidable in polynomial time also recursively enumerable?

If both are RE then this makes P recursive?

co-$\mathsf{P} = \mathsf{P}$. To see this, pick your favorite problem $A$ in co-$\mathsf{P}$, let $T$ be a Turing machine for the complement of $A$ (in $\mathsf{P}$) and construct a new Turing Machine $T'$ that simulates $T$, accepts if $T$ rejects, and rejects if $T$ accepts.


What does superscript + mean in relational algebra? What does superscript + mean in relational algebra?  Suppose $A$ is a subset of attributes of all attributes in a relation $R$.  What does $A^+$ mean?

I got the answer.  $A^+$ represents the set of attributes that $A$ functionally determines.


Snap/Fit a chain of lines to points I am looking for an algorithm to fit a chain of lines to a set of points/pixels. I am pretty sure that there is a suitable algorithm but I can't think of the correct search words to find it.
Here is an image to illustrate what I want:

The figure shows a chain consisting of 3 individual lines. The lines are always connected, but their connecting points can be moved. The goal is to fit the connecting points such that the resulting lines are in a sense optimal with respect to the points/pixels (here in black with blue border), for example minimzing some distance. It would be nice if one could adapt this optimality criterion, e.g., such that the lines might snap to the point cloud coming from below the point cloud.
In my current problem I could also give some side conditions for the connecting (yellow) points, such as: point 1 has to be somewhere between x and y on the horizontal axis. Also, I could give conditions on the angles between the lines.
It would be awesome if someone could point me in the right direction and tell me actually what I am looking for :)

Yes.  This is eminently doable.  Here's the general recipe:

Define an "loss function" $L$.  The loss function takes as input the location of the connecting points, and it outputs a measure of how good/bad this set of connecting points is.  Smaller is better.  You mention "minimizing some distance"; this is where you put that, but you'll need to decide on a specific loss function you want to minimize.  If there are four connecting points, the loss function will take the form $L((x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4))$ and will output a single real number.  Choose a function that is continuous and differentiable.
Use gradient descent to find a location for the connecting points that minimizes the loss function.  Pick some reasonable initialization value (e.g., where the user initially drew the lines; or use some heuristic to pick a crude guess at where to put the connecting points), and then use gradient descent to improve this initial choice and find a minimum for $L$.

This should be very efficient.  It's also very flexible: if you decide you want a different criterion for what the line should look like, you achieve that by modifying the loss function.  There are standard libraries for gradient descent, or if you prefer, you can implement it yourself without too much difficulty.


Do we need to check for mantissa overflow in floating point multiplication? We do check for the mantisas overflow in floating point addition

e.g.

If we are adding $8.02 \times 10^3 + 9.01 \times 10^3 =17.03 \times 10^3$ i.e we get an overflow, so we shift the number right and increase the value of exponent.

But does it occurs during floating point multiplication?

According to my logic, it should occur. because $9.99\times9.99=99.80$ which is a mantissa overflow, but that's not the case.

I have referred to Morris Mano's books and William Wtallings Computer Organization and Architecture book but none of those books mentioned about floating-point multiplication mantissa overflow.

So I feel like I am wrong.

Please tell me where I am wrong?

When we multiply, the answer is stored in 2 registers. When we multiply 2 numbers the results length does not exceed  ($n_1+n_2$) where $n_1$ is length of 1st number and $n_2$ is length of second number. So there is no chance of overflow here as the length of 2 registers is greater than or equal to $n_1+n_2$.


Defining the goal function in an optimization problem I have an optimization problem. There are a few quantities, call them $a, b, c$, that describe how good a solution is. However, they all have different priority, from highest to lowest: $a, b, c$.

The goal is to minimize the values of $a, b, c$. The difference in priorities means that the solution with identical value of $a$, lower value of $b$ is lower than the other solution, no matter what the value of $c$ is. Similarly, if the value of $a$ is lower, then no matter what $b$ or $c$ is, the solution is better better than the other solution.

What's the best way to define a goal function for this problem? I don't know the range of those values. I was thinking about using some weight parameters, like multiplying $a$ by the greatest weight, $b$ by lower weight, and $c$ by the lowest weight value.

If you know the minimum and maximum values for $a,b,c$, you can use a weighted linear combination.  e.g., if $a,b,c \in [0,1000]$ (they are all between 0 and 1000), then you can use the objective function

$$\Phi(a,b,c) = 10^6 a + 10^3 b + c.$$

Minimizing this function is guaranteed to be optimal under your partial order.

Sometimes, even when you don't have upper and lower bounds, you can still use an objective function like the one above, as a heuristic.  It's not guaranteed to give optimal results, but it might be good enough in your particular application.


Two peaks finding algorithm We are given an array of length N with exactly 2 peaks (a peak is an element which is no less than the left and right neighbors). Is there an algorithm to compute those peaks faster than O(N), maybe similar with the single peak finding in O(log N)?

No. Any algorithm to locate those two peaks will take $\Omega(N)$ time, assuming that the only operation allowed is to compare two elements in the array, i.e., the comparison mode.

Otherwise, suppose algorithm $A$ do not need that much time. Let $arr[0], arr[1], \cdots, arr[N-1]$ be the given array. Then for some $N$ large enough, $A$ will have only checked at most $N-3$ elements before it has terminated. Suppose for all comparisons that have done by $A$, it will be found that $arr[i] < arr[j]$ where $i<j$.

Let $arr[a], arr[b], arr[c]$ be three elements that have not been checked yet, $a<b<c$. Whatever $A$ have done, the two peaks could be $\{arr[a], arr[N-1]\}$. They can be $\{arr[b], arr[N-1]\}$ as well. Since $A$ cannot distinguish these two cases, $A$ cannot possibly have determined the two peaks.

Exercise. (less than one minute) Modify the above argument so that it becomes valid in the case when a peak must have both left neighbor and right neighbor.


Why does a regular expression only accept all my required strings when the concatenation is the first of the OR operations? I am having a bit of difficulty understanding the order of precedence in boolean logic for the OR operation. Take this example:

Assume the following regular expression:

((a(b+))+(a|c))|a|c

Why is it that this accepts the strings:

a
c
abba
abbabbba
abbabbc

etc

But when I flip it around and use the regular expression

a|c|((a(b+))+(a|c))

I can now only ever get the following strings when I check it with a RegExp tester:

a
c

I know it is to do with the order of precedence but I don't understand why, please could somebody enlighten me?

Both the patterns match your given strings and are equivalent. The problem here is that your tester does not try to match the string against the pattern, but tries to find matching substrings, and it does that by trying each of the ORed patterns in order. Hence the second pattern stops when $a$ is matched, but the first one matches the whole string.

To see the difference Look at the below code, written in Java:

public static void main(String[] args) {
    test("((a(b+))+(a|c))|a|c", "abbabbc");
    test("a|c|((a(b+))+(a|c))", "abbabbc");
}

private static void test(String pattern, String str) {
    System.out.println(str.matches(pattern));
    Matcher matcher = Pattern.compile(pattern).matcher(str);
    while(matcher.find())
        System.out.println(str.substring(matcher.start(), matcher.end()));
}

The output is

true
abbabbc
true
a
a
c

which shows that both patterns do match $abbabbc$. They are only different in eyes of a matching-substrings-finder program.


Is it possible to use dynamic programming to factor numbers Let's say I am trying to break all the numbers from 1 to N down into their prime factors. Once I have the factors from 1 to N-1, is there an algorithm to give me the factors of 1 to N using dynamic programming?

You can try to find the smallest divisor $d>1$ of $N$ by trial divison. Then the factorization of $N$ is given by that of $d$ and that of $N/d$. Since $N$ is either a prime number or has a divisor $1 < d < \sqrt{N}$, this would solve the problem. Of course, this is a dynamic solution in a very vague sense only - the table of partial results is only used as a cache, not like in "real" dynamic programming algorithms.


Are hash functions one-way? I have heard that we can convert any text to hash code , but hash code can't be converted back to text without brute force.
Suppose we consider the text "mal". The hash codes of the individual letters are

m= 6f8f57715090da2632453988d9a1501b
a= 0cc175b9c0f1b6a831c399e269772661
l= 2db95e8e1a9267b7a1188556b2013b33

Those of the prefix "ma" and of "mal" itself are

ma= b74df323e3939b563635a2cba7a7afba
mal= 749dfe7c0cd3b291ec96d0bb8924cb46

Each hashcode has 32 elements, which can be either numbers from 0 to 9 or letters from a to f.
What I observed was some when we add a letter some numbers are kept like it is just changing it's order. Is there some logic in it? Is there some easier method?

Well, there is obviously a system. Someone wrote code to calculate the hash codes for strings, and that is the system that the hash code follows.

For normal software development purposes, it's Ok if there is a system that you can recognise, as long as different strings are mapped to different hash codes most of the time. For cryptography, for example when you calculate a hash code for a password, you want hash codes where it is practically impossible to determine the string from the hash code.

For a cryptographic hash, given a hash h, the only way to find a string s with hash(s) = h is to try out all possible strings s calculating hash(s) for each, until we find an s with hash(s) = h. Given a cryptographic hash for the string "1234", you would find such an s quickly.

For ordinary hash functions, if you are given how the hash code is calculated, it is often possible to calculate which is the shortest string s with hash(s) = s. However, any function that maps from an infinite set (strings) to a finite set (fixed length hash codes) must allow many strings to map to the same hash code. So if you map 500 bit strings to 256 bit hash codes, you cannot possibly determine which string was hashed, because many strings have the same hash code.


Reduction from an assignment problem to an independent set problem: NP-hard The problem I have is as follows:
I have a complete bipartite graph $G=(V \cup C,E)$ as input, where $|V|=1, |C|=n, |E|=n$
The interpretation is that the node of $V$ is a vehicle, the $n$ nodes of C are incidents and the $n$ edges from $V$ to $C$ are the travel times from the vehicle to the incidents.
Now the incidents occur at a certain time and due to that not all incidents can be assigned to the vehicle. Every incident induces a set $D_i$ that consist of incidents that may not be assigned to the vehicle if incident $i$ is assigned to the vehicle:
$D_i = \{k|\text{incidents $k$ that may not be assigned to the vehicle if incident $i$ is assigned to the vehicle}\}$
Out of the sets $D_1, \dots , D_n$ a 'Forbidden Incident' Graph $G=(C,E)$ can be constructed where an edge $(h,i)\in E$ if ($i \in D_h$ or $h \in D_i$).
See the following figure as an example:
Forbidden Incidents Graph

So the problem is: Give a set of incidents, is this set an independent set in the forbidden incident graph?
It is known that an Independent Set problem is NP-hard. Now I aim to proof the conjecture that this problem is also NP-hard.

So I want to find a reduction from my problem to the independent set problem.

Any hints?

If you want to show that your problem is NP hard, your reduction should go in the other direction. You have to show:
$\exists L \in NPH: L \le_M yourProblem$
where $NPH$ is the Set of NP-hard languages.

Your try looks like you wan't to reduce from your problem to Independent Set.


$MIN_{NFA}$ is PSPACE complete The problem is taken out of Theory of Computational Complexity:

Now, I think I've successfully proven that $ALL_{NFA} = \{(A) :  A$ is an NFA and $ L(A) = \Sigma^*\} \leq_p MIN_{NFA}$. Which implies that $MIN_{NFA}$ is PSPACE hard, as the latter is itself.

However I'm stuck proving this problem is in PSPACE - I've thought of defining a nondeterministic Turing Machine, that takes an NFA and a natural number $n$ as input, and on each branch of the computation creates a NFA with number of states less than or equal to $n$. This machine will go on to compare the resulting NFA (in each branch) to the given one (this problem is itself in PSPACE, but I've yet to prove it myself).

However it seems to me the above idea may use more than poly. time, as we may have to keep track of the transition function of each NFA; whose image is in the power set of its states.

Any assistance?

For a fixed alphabet, you can describe an NFA with $n$ states using $O(n^2)$ bits. Now, given a DFA $M$ and an integer $n$ (encoded in binary), we consider two cases:

$M$ has at most $n$ states. In this case, there exists an NFA for $L(M)$ having at most $n$ states.
$M$ has more than $n$ states. In this case, the input length is $\Omega(n)$ bits, and so we can guess an NFA with $n$ states in polynomial space.


How to analyze the lower bound of the horse racing problem using adversary argument? Consider the following problem:

  Give an algorithm to find the $1^{st}, 2^{nd}, 3^{th}$ fastest horses from 25 horses. In each round, at most 5 horses can race and you can get the exact position of these horses. Analyze the lower bound of this problem using adversary argument. One race is considered as one critical operation.

I can figure out a solution using 7 races:

  Divide 25 horses into 5 groups with 5 horses for each: $A: a_1, a_2, a_3, a_4, a_5$; $B: b_1, b_2, b_3, b_4, b_5$; $C: c_1, c_2, c_3, c_4, c_5$; $D: d_1, d_2, d_3, d_4, d_5$; and $E: e_1, e_2, e_3, e_4, e_5$.
  One race within each group. Suppose that the position of each horse in each group is consistent with its index: e.g., $A: a_1 > a_2 > a_3 > a_4 > a_5$.
  One race for $a_1, b_1, c_1, d_1, e_1$ and get $a_1 > b_1 > c_1 > d_1 > e_1$. Thus, $a_1$ is the fastest horse.
  The second and third ones are among $a_2, a_3, b_1, b_2, c_1$. So one more race is enough.

However I have difficulty in analyzing its lower bound using adversary argument.
So my problem is:

  How to analyze its lower bound using adversary argument? What is the adversary strategy?

Intuitively, the reason you need $7$ comparisons is that (1) you need $5$ comparisons just to see all the horses, (2) you need to compare all the first ranked horses to see which one is the fastest, (3) at this point you can't tell which is the second ranked horse.

Of course, this is not quite an adversary argument, and some work will be needed, though it is easy to use an adversary argument to show that (1) is correct: suppose that the strategy involves less than $5$ comparisons; then you don't see all the horses; so you can't tell whether the fastest horse is one of those you've seen or not. (Formally, if the algorithm states that a horse it's seen is the fastest, then you arrange for one of the one it didn't see to be the fastest; and vice versa in the other case.)

The same argument can be extended to show that $5$ comparisons are not enough: the only way that $5$ comparisons could be enough is by executing step 2 of your algorithm, and then you cannot tell which horse is the fastest. (I'll let you formalize that.)

I'll let you complete the argument and show that $6$ comparisons are also not enough.


How to show that this decision problem is in co-NP? Given a set of strictly positive numbers $a_1, ..., a_n$, the problem is to determine if $\lfloor n/2 \rfloor$ different indexes $i_1, ..., i_{\lfloor n/2 \rfloor}$ exist so that $$\frac{a_{i_j}}{a_{i_{j-1}}} = \frac{a_{i_{j+1}}}{a_{i_j}}$$ for $2 \leq j \leq \lfloor n/2 \rfloor$.

How to show that this problem is in co-NP ?

P is a subset both of NP and of co-NP. Do you think the problem is in P?

(O(n^3) solution is trivial if poster states the problem correctly. As it is, $i_1 = i_2 = i_3  ... = 1$ is a solution.)

You need n/2 different indices $i_j$ such that $a_{i_2} / a_{i_1} = a_{i_3} / a_{i_2}$, $a_{i_3} / a_{i_2} = a_{i_4} / a_{i_3}$, etc.

There are $n^2 - n$ ways to choose $i_1$ and $i_2$. Once you chose these, let $d = a_{i_2} / a_{i_1}$. Then we must have $a_{i_3}$ = $a_{i_2} \cdot d$, $a_{i_4}$ = $a_{i_2} \cdot d^2$, $a_{i_5}$ = $a_{i_2} \cdot d^3$ etc. So all you have to do is check whether there are enough $a_i$ with these values and take their indices.

You can do this faster, but all I cared about was whether it's polynomial time.


If a problem is PSPACE-complete what do we know about NL-completeness I have a problem $A$ which was shown to be PSPACE-complete by reduction from planning.
However, $A$ can also be transformed into reachability problem which is NL-complete.

I know that $NL=NSPACE(log \ n)$ and $PSPACE=NSPACE$.

Does this mean $A$ is also NL-complete? IF yes, does it make any difference in this context to say whether $A$ is PSPACE-complete or NL-complete ?

A PSPACE-complete problem cannot be in NL, and in particular cannot be NL-complete (this is a consequence of the space hierarchy theorem). However, it is NL-hard. If $A$ can be transformed into a reachability problem, then probably the transformation is not polynomial-time.


What is the connection between data structures and data types? I have read some books and wikipedia, which seem to give not completely consistent definitions and notations. I try to understand the concepts, regardless of what they are called. Here are what I have figured (please correct me) and would like to ask :

a (abstract) data type is a set $D$ of values, together with some
operations on it (each $n$-ary operation is a mapping $D^n \to D$).
E.g. The set of all the integers with arithmetic operations on it forms a data type.
A data structure seems to be a data type. Or are they the same
concept? What is the formal definition of a data structure?
I have some difficulty in understanding if a "container-like construct" is a data structure or data type, or the set of all of them is. What I mean by a "container-like construct", is some set of values, but with some relation(s) on the set, e.g. a queue, a graph, a stack, an array, a map, .....

E.g., a queue is a set of values in it, with some ordering on the values according to which value was added earlier than which. Is a queue with a fixed size and fixed elements, as a set of values in it,  a data type or a data structure?  Or do all the queues form a data
type or a data structure? Are adding and removing elements from a
queue, which obviously create new queues, viewed as operations on the set of all the queues?

Similarly, a graph is a set of vertices and has relation between the vertices being the edges. Is a graph with fixed vertices and edges a data type or a
data structure, or is the set of all the graphs a data type or a
data structure? Are transformations from a graph to another different graph  considered to be operations on the set of all the graphs? Is searching for a vertex in a graph considered to be an operation on that single graph?

I agree with your definition of abstract data type.  (A domain of values, together with some operations on that domain.)

I typically use the term data structure to refer to implementation techniques for data types.  Examples of data structures are things like balanced binary trees and hashtables.

For example consider the data type set of integers, with operations like union, intersection, is_member?, and insert_member.

You could implement the data type with at least three different data structures, each of which has advantages and disadvantages.  For example, you could implement your set using a balanced binary tree (like a red-black tree, for example).  Each node in the tree represents a member of the set, insertion and membership tests take $O(\log n)$.  Or, if your sets are over a finite (and relatively small) universe of items you could implement it with a bit array.  This is an array of $U$ bits (where $U$ is the size of the universe.) Inserting element $i$ just means setting the $i$th bit, testing for membership just means testing the $i$th bit.  But now intersection (respectively union) requires you to take the binary-and (respectively or) of $U$ bits, which kind of stinks when you have sets with just a few elements in them.  Similarly with hash table implementations, insertion and testing are nice (on average), but intersection and union can be somewhat more complicated to do efficiently.


Why databases make the distinction between basic logical operations and functions It just occurred to me that things like "greater than or equal to" and other "logical operators" are also just simple functions, such as gte(a, b) == a >= b. This makes me wonder why these are treated as "special" in databases and why they are not just functions like SQL functions. Wondering if there is some advantage to treating them differently like they do.

Database indices are typically binary search trees, meaning you can do range queries on them very efficiently.  If you handed the database the >= relation as a black box, on the other hand, it would have to iterate over every single record in the table performing the check.


On $L^* - \{\epsilon\} = L^+$ $\Sigma^* - \{\epsilon\} = \Sigma^+$

  $L^* - \{\epsilon\} = L^+$

  Which of the above is always true?

I was following a discussion on a site and I came across this question. Some fellow scholars claimed that the second statement is not always true.
The answer they provided is this:

  $S_1$: $Σ^* – \{ϵ\} = Σ^+$: TRUE  // Always true, definition of $Σ^+$

  $S_2$: $L^* – \{ϵ\} = L^+$: FALSE // May or may not be true

  False when $ϵ$ belongs to $L$, then $L^+$ and $L^*$ will both contain $ϵ$.

  PS: In $S_2$, it depends purely on the given language.

But I have this doubt:

How can $L^+$ contain $ϵ$? we obtain $L^+$ by deleting $ϵ$ from $L^*$, and in $L^*$ of the language where $L=\{ϵ\}$, $L^*$ will only contain $ϵ$, so if we remove $ϵ$ from it, then the language should become $\emptyset$, which is nothing but $L^+$ here. So shouldn't the second statement also be true?

Say $L^+  = \{ϵ,ϵϵ,ϵϵϵ,\dots\}$.

Now an important point. Note that we say Set of all strings, now in set theory duplicates are not allowed, moreover $ϵ= ϵϵ =ϵϵϵ =\dots$. They are all just the same. So $L^∗$ should be only $\{ϵ\}$, rather than $\{ϵ,ϵ,ϵϵ,ϵϵϵ,\dots\}$, right?

You got the definition of $L^+$ wrong. It is not $L^* \setminus \{\epsilon\}$. Rather, it is
$$
L^+ = \bigcup_{n=1}^* L^n.
$$
You can check that $\epsilon \in L^+$ iff $\epsilon \in L$. Therefore:

If $\epsilon \notin L$ then $L^+ = L^*\setminus\{\epsilon\}$.
If $\epsilon \in L$ then $L^+ = L^*$.


Turing Machine state going to itself Hey guys in a turing machine can a state go to itself by reading a letter. For example,

q2 reading a 'c' to go to itself. Is that possible?

Or does it need to read a tape alphabet, such as $ to read that c and then go back to q2?

Yes, a state can go to itself when seeing any symbol. (As Steven's answer says, the analogous question for head movement - whether the head of the Turing machine has to move at each stage, or whether it can stay put at a given moment - varies from definition to definition, but I've never seen a definition which prohibits a state from looping to itself.)

Note that this is a particularly natural thing to allow: it's basically a "while" command.

However, as with many aspects of Turing machines, tweaking the definition to rule it out isn't significant: Turing machines which prohibit states from looping to themselves are no weaker than Turing machines which allow states to loop to themselves. This is a good exercise.


Algorithm for multiplying multivariate polynomials Let $R$ be a commutative ring. Let $f(x_1, \dots, x_n), g(x_1, \dots, x_n)$ be two multidimensional polynomials in $R$ with maximal total degree $\delta$.
How fast can we compute the product of $f$ and $g$, i.e. the resulting coefficients of each term?

I have only been able to find a non-trivial algorithm for when $R$ is a field of characteristic 0, but not for $R$ being a general commutative ring.

There is a general method for efficient multiplication in any ring. This would cover the case where the degree is bounded in each dimension separately, because a polynomial $p\in R[x,y]$ in variables $x$, $y$ over the ring $R$ can be interpreted as a polynomial $p\in R[x][y]$ in the variable $y$ over the ring $R[x]$. This is essentially the case I thought about in my comment above. However, the total degree limitation from the question requires a different method. Such total degree limitations occur for determinants and permanents, but have little to do with convolution. It is not even covered in the general overview of multiplication algorithms. At least we may assume WLOG that the ring has has characteristic $p^m$ or 0, because it is easy and canonical to decompose a ring into simpler rings (and because factoring the characteristic is not part of the cost of multiplying two polynomials, even if it might be more expensive than the multiplication itself).

For $n\geq 2\delta$, the resulting polynomial $fg$ can have up to $2^{2\delta}$ monomial terms. For $R=\mathbb Z$, the coefficients of the monomial terms can all be different, so we can't do better than $O(2^{2\delta})$. The question had probably something like $O(N^2)$ versus $O(N \log N \log \log N)$ in mind. But if $N$ would measure the number of coefficients (of monomial terms) of the input polynomials $f$ and $g$, then $O(N^2)$ would be the optimal worst case bound. But what should $N$ measure instead?

Let's assume that $fg$ is determined uniquely by its values $fg(\underline{x}^1),\ldots,fg(\underline{x}^N)$ for suitable points $\underline{x}^1,\ldots,\underline{x}^N$. Then a possible way to compute $fg$ is to evaluate $f$ and $g$ at the points $\underline{x}^1,\ldots,\underline{x}^N$, multiply these values pointwise, and then determine $fg$ from these products. This is more or less also what happens when the FFT is used to compute a convolution.

The paper On Zeros of a Polynomial in a Finite Grid cited in the recent answer by Anurag Bishnoi gives sharp bounds on the number of zeros of a polynomial on a finite grid satisfying condition (D). A nonempty subset $S \subset R$ is said to satisfy Condition (D) if for all $x\neq y\in S$, the element $x−y\in R$ is not a zero divisor. For $n \in \mathbb Z^+$ we put $[n] = \{1,2,\ldots,n\}$. We have

  Theorem 1.2 (Generalized Alon-Füredi Theorem). Let $R$ be a ring, and let $A_1, \ldots, A_n$ be non-empty finite subsets of $R$ that satisfy Condition (D).
  For $i \in [n]$, let $b_i$ be an integer such that $1 \leq b_i \leq \#A_i$. Let $f \in R[\underline{t}] = R[t_1,\ldots,t_n]$ be a non-zero polynomial such that $\deg_{t_i} f \leq \# A_i − b_i$ for all $i \in [n]$. Let $\mathfrak U_A = \{x \in A : f(x)\neq 0\}$ where $A=A_1 \times\dots\times A_n \subseteq R^n$. Then we have (see §2.1 for the notation)
  $$\# \mathfrak U_A \geq \mathfrak m(\#A_1,\ldots,\#A_n;b_1,\ldots, b_n;\sum_{i=1}^n\#A_i −\deg f).$$
  Moreover, this bound is sharp in all cases.


Time complexity of functions that call each other I'm having trouble reasoning about the time complexity of these mutually recursive functions. This was asked on SO here but the answer there didn't help me. I tried substituting one of the recurrences in the other but because they are mutually recursive I got stuck. I tried writing out the function calls for x=10 but I'm stuck making sense of that too. How do I go about working through something like this?

int foo(int x)
{
  if(x < 1) return 1;
  else return foo(x-1) + bar(x);
}

int bar(int x)
{
  if(x < 2) return 1;
  else return foo(x-1) + bar(x/2);
}

Edit: With @quicksort's answer I get S(n) = 2*S(n-1) + S(n/2) - S(n/2-1) and if I try to solve it using Wolfram I'm seeing something different: solution . Also, it's not intuitive to me that this is exponential. How does one see that?

To help with your intuition, change the code by substituting the code for bar into foo:

int foo(int x)
{
  if(x < 1) return 1;
  else if (x < 2) return 2; // foo(0) + bar(1), x = 1
  else return foo(x-1) + foo(x-1) + bar(x/2);
}

int bar(int x)
{
  if(x < 2) return 1;
  else return foo(x-1) + bar(x/2);
}

So now it is obvious that T (x) ≥ $Θ(2^x)$, since foo (x) does two recursive calls to foo (x-1). Also makes it obvious that the result is foo (x) ≥ $Θ(2^x)$, and that result can be calculated in linear time.


Mathematical optimization on a noisy function Let $f:\mathbb{R}^d \to \mathbb{R}$ be a function that is fairly nice (e.g., continuous, differentiable, not too many local maxima, maybe concave, etc.).  I want to find a maxima of $f$: a value $x \in \mathbb{R}^d$ that makes $f(x)$ as large as possible.

If I had a procedure to evaluate $f$ precisely on any input of my choice, I could use standard mathematical optimization techniques: hill-climbing, gradient descent (well, gradient ascent), etc.  However, in my application I don't have a way to evaluate $f(x)$ exactly.  Instead, I have a way to estimate the value of $f(x)$.

In particular, given any $x$ and any $\varepsilon$, I have an oracle that will output an estimate of $f(x)$, and whose expected error is approximately $\varepsilon$.  The running time of this oracle invocation is proportional to $1/\varepsilon^2$.  (It is implemented by a kind of simulation; the accuracy of the simulation increases with the square root of the number of trials, and I can choose how many trials to run, so I can choose the desired accuracy.)  So this gives me a way to get an estimate of any accuracy I desire, but the more accurate I want the estimate to be, the longer it will take me.

Given this noisy oracle for $f$, are there any techniques for computing a maxima of $f$ as efficiently as possible?  (Or, more precisely, finding an approximate maxima.)  Are there variants of hill-climbing, gradient descent, etc., that work within this model?

Of course, I could fix a very small value of $\varepsilon$ and apply hill-climbing or gradient descent with this oracle, keeping the same $\varepsilon$ throughout.  However, this might be unnecessarily inefficient: we might not need such a precise estimate near the beginning, whereas precision near the end when you are zeroing in on the solution is more important.  So is there any way to take advantage of my ability to control the accuracy of my estimate dynamically, to make the optimization process more efficient?  Has this kind of problem been studied before?

One could replace the exact function $f(x,p)$ by the noisy function $f(x+\Delta x, p + \Delta p)$, where $p$ is an artificial parameter used to describe the noise dependency such that $\Delta x$ and $\Delta p$ contain the noise.

Some techniques used in stochastic optimization and robust optimization might be applicable.
Because $\frac{\partial f}{\partial x}\approx 0$ near the maxima, $\Delta x$ is less dangerous than $\Delta p$.
Sometimes $\frac{\partial f}{\partial x}(\tilde{x}, \tilde{p})$ can be approximated accurately while evaluating $f(\tilde{x}, \tilde{p})$. Often, this is only true in theory, because it is not implemented, and some parts would require special care.
The desired "smallness" of $\Delta p$ (and $\Delta x$) is an "end user" decision. One can offer heuristics to control it, but a runtime proportional to $1/\epsilon^2$ is too slow for fully automatic accuracy handling.
The given noise vs runtime tradeoff is what sets this problem apart from better studied problems. Problems were the noise is just unavoidable are more common and better studied.


What is this trapezoid-shaped logic component? This is from http://www.cis.upenn.edu/~milom/cse240-Fall05/handouts/Ch05.pdf , slide 9.

From this diagram, I recognize 0001 as the opcode, which corresponds to the ADD instruction. I recognize 011, or 3, as the source register and 101, or 5, as the destination register. I know that the 1 signifies immediate mode or the second operand is directly in the instruction. From here, I know that the second operand is 11111 or -1 in decimal and that it will be sign extended (SEXT) before being added to the data in the source register.
Does anyone know what the logical component I highlighted does?

The component is shaped like an isosceles trapezoid, and has three inputs: seemingly, two data inputs and one control input.

Looking at slide 5-43 "Data Path Revisited" these are MUX, multiplexors.

As such they are a "switch": When the red input is 1, we have immediate mode and the SEXT output is passed through unchanged. When it is 0 it needs to look up a value based on the SEXT value and some memory or register.

Also in the slides, a MUX is represented again at BR and JMP, slides 5-31 and 5-35, again without actually clearly defining the alternative scenarios, and the BR case confuses the issue a bit because it clearly calculates a relative jump previously.

I'd guess the red input is the result of the branch condition and if false the original PC is passed through, but if that was the case they might as well have connected up the lines in this diagram.

For the JMP it is currently showing an absolute jump and under a different red arrow input it could be an indirect jump, similar to the ADD case.

(My latter suggestions have not actually been reconsidered much after reviewing slide 5-43.)


Does Herbrand's theorem mean any first-order logic formula can be expressed in CNF? Herbrand's theorem shows that any formula of first-order logic can be expressed as a disjunction of quantifier-free formulas of first-order logic.

Is this equivalent to saying that Herbrand's theorem shows that any first-order logic formula can be expressed in Conjunctive Normal Form (CNF)?

Well, that's not really what Herbrand's theorem says.  That's not a good way to think about Herbrand's theorem.  To understand the answer to your question, you first need to understand a little better what Herbrand's theorem does and doesn't imply.

I suspect I know what you are thinking.  You are thinking, given a statement $\varphi$ of first-order logic, you can find a disjunction $\psi_1 \lor \dots \lor \psi_k$ of quantifier-free formulas that is equivalent to $\varphi$.  However, that's not really what Herbrand's theorem says.  Herbrand's theorem doesn't necessarily give an effective or easy way to find the disjunction.  Herbrand's theorem says that if $\varphi$ is true, then there exists such a disjunction, but to actually find the disjunction, you have to know that $\varphi$ is true, and you have to know a proof that it is true (roughly speaking).

Let me give you an example and an analogy that may clear things up.  Here is D.W.'s theorem:

D.W.'s Theorem. Any formula of first-order logic can be expressed as either True or False.  In other words, for every sentence $\varphi$ of first-order logic, there is a formula $\psi \in \{\text{True}, \text{False}\}$ such that $\varphi$ is valid if and only if $\psi$ is valid.

D.W.'s theorem is trivially true; I can prove it in a single line.  Pretty cool, huh?

However, D.W.'s theorem is actually not very useful.  Given a formula $\varphi$ of first-order logic, D.W.'s theorem doesn't help you figure out whether $\varphi$ is valid or not.  Similarly, Herbrand's theorem doesn't really help you figure out whether $\varphi$ is valid or not.

Now, the formula $\text{True}$ is in Conjunctive Normal Form.  Also, the formula $\text{False}$ is in Conjunctive Normal Form.  Therefore, by D.W.'s theorem, every sentence $\varphi$ of first-order logic is equivalent to some quantifier-free formula $\psi$ in CNF form.  However, this probably not the kind of equivalence you were hoping for, because given $\varphi$, it's not necessarily easy to compute the $\psi$ that is equivalent to $\varphi$.


would complexity of constraint satisfaction problem bound the constrained optimization problem? If a constraint satisfaction problem $x \in Y$ is NP-Complete.
Can I conclude that the optimization problem $^* =\text{argmax}_x (x)$ s.t. $x \in Y$ is also NP-Complete?

No, no optimization problem can be $\mathsf{NP}$-complete since all $\mathsf{NP}$-complete problems are in $\mathsf{NP}$ and $\mathsf{NP}$ only contains decision problems.


How to estimate floating-point precision of function? Let's say I have a function that consists solely of floating-point operations where the last operation rounds the computed value to a predefined number of digits. And I feed this function with a range of floats.

How do I conclude - just by looking at the decimals of the operand(s), and the structure of the code / sequence of floating-point calculations - that the round-up errors may or may not yield an unexpected result?

Do you know of any rule of thumb or mathematical methodology? Anything I can put to general use? I don't want to actually test the code.

Just one example for reference; range of input, required precision, and implementation of calc() are arbitrary:

Input: 0, 0.01, 0.02 ... 999.98, 999.99, 1000 (delta = 0.01)

Required precision: Rounded accurately to 2nd decimal

Pseudo code:

function main(a) {
  res = calc(a);
  return round(res); // Rounds res to desired decimals
}

function calc(a) {
  float b = 1.1;
  return a * b;
}

Update #1:

I found an interesting blogpost on the topic: Introduction to Scientific Computing: Error Propagation

It seems to contain the mathematical tools one needs to evaluate how "error prone" a computation is.

Update #2:

I worked out the following method to estimate the error propagation and will describe how I applied it on my use case.

It would be great if you comment on my thoughts. I'm not sure if I did it right. And thanks for your help so far! :)

Pseudo code:

// Floats conform to IEEE 547

function main() {
  float a,b; // Real value between 199 and 684
  a = some_value;
  b = another_value;
  res_a = calc(a);
  res_b = calc(b);
  res = res_a + res_b;
  return round(res); // Rounds to 2nd decimal
}

function calc(x) {
  float c = yet_another_value; // Real value between 1 and 1.4
  return c * x;
}

Estimation:

As I'm using IEEE 547 floats, the machine epsilon ε is 1.1e-16.
The relative error δ is 2ε - according to the article linked under update #1.
So the absolute error of my maximal input emax won't exceed 3.8304e-13. *
That means the result will be precise up to the 12th decimal.
Since I just desire a precision of 2, the calculation does work precisely enough.

*) emax = 2ε * resmax = 2 * 1.1e-16 * 2 * 684 * 1.4 = 3.8304e-13.

Bonus consideration:

Q: Would one add up the results of calc() infinitely, how many results would be "needed" approximately to contaminate the rounded total?

A: One would have to call calc() at least 4 trillion times. \o/

e has to be at least 0.001 to force a round-up error
The maximum result of calc() is xmax = 684 * 1.4 = 957.6
e = δ * x => x = e / δ = e / 2ε = 1e-3 / (2 * 1.1e-16) = 1e+13 / 2.2
n = x / xmax = 1e+13 / (2.2 * 957.6) ≈ 4e+9

Assuming that you're rounding from the thousandths place, the code in your example will always be accurate. Floating point numbers remain useful because they keep their imprecisions quite small relative to the most significant digit.

For instance, using the 8-byte IEEE754 standard (doubles in Java), 10.0/3.0 becomes3.3333333333333335.

You also asked for a rule of thumb to quickly determine whether your math will be accurate. Assuming that you are using the 8-byte standard, you can reasonably guess whether the calculation you are doing will be inaccurate by remembering that inaccuracies begin roughly 15-16 digits beyond the largest digit.  If you're using the 4-byte standard (like you did in your example), you only get about 7-8 digits beyond the largest digit.

With that understanding, you can easily spot places you might run into trouble.  If you're going to use a loop to multiply your number repeatedly, and then check whether the 1s digit is even or odd, you will likely run into inaccuracies.

One slightly surprising way to find trouble is to check simple equality.  Consider the following Java code:

double x = 10.0;
double y = 3.0;
System.out.println( (1*x/(y*1)) == (10*x/(y*10)) );

It ultimately prints false, because it is really testing 3.3333333333333335 == 3.333333333333333. So, for equality testing, you will need to make some decisions about levels of precision, and run some rounding algorithm to obtain that.