Closest arithmetic progression to an array Given an array of $N$ integers, having the option to increase or decrease its elements, the problem is to find the closest integer arithmetic progression. That corresponds to the smallest difference between the elements of the array and the elements of progression. Thus one needs to minimize the sum of absolute differences. It is a restriction that the values must be integers:
$1, 5, 10, 14, 19 \to 0, 5, 10, 15, 20$

It is easy to solve it with the help of linear programming without restriction to integers. But even the simplex method and other similar algorithms are not sufficient because they can handle cases when $N \leq 10^5$. In this case, the integers can be rather large (i believe up to $10^7$). Is there any algorithm for solving it in $O(N\log^k M)$ or even $O(N)$, where $M$ is the maximum integer value of an array?

Let's call your array $a$. The goal is to find $x,k$ such that $\sum|a_i-(ix+k)|$ is minimized. Fix $x$ and replace $a_i$ by $b_i=a_i-ix$. Now the goal is to minimize $\sum|b_i-k|$, so $k$ is obviously the median of $b$. Since it's not hard to solve this problem with fixed $x$, it's natural to consider if there's any monotonicity on $x$.

Note that the error can be written as $\sum_{b_i\in upper\,half}b_i-\sum_{b_i\in lower\,half} b_i$. Substitute $b_i$ by $a_i-ix$ and we'll get a formula like $c-(\sum_{b_i\in upper}i-\sum_{b_i\in lower}i)x$, which is linear. The optimal $x$ can be found trivially in this case, but the order of $b$ changes when $x$ incerases (decreases). Let's see how it changes.

Scan $x$ from negative to positive. At some points a "swap" may happen: originally $b_i<b_j$ but after this point $b_i>b_j$. This only happens when $i<j$. If they are originally in the same half then nothing happens. But if originally $i$ is in the lower half and $j$ is in the upper half, now $i$ moves to the upper half and $j$ moves to the lower half. This increases the slope by $2(j-i)$. Median should be excluded from both halves if $N$ is odd but the conclusion "slope is increasing" remains.

Now we know the error is a convex function so we can find the minimum by ternary search on $x$. Since we can compute the error in $O(N)$ if we fix $x$ and the range of $x$ is bounded by $O(M)$, the total complexity  is $O(N \log M)$. (Here I consider the cost of each arithmetic operation as a constant.)


Can one use the PCP theorem to prove correctness of deternimistic algorithms? I am thinking of the equality "PCP(O(log(n)),0) = P"

Say I have a deterministic polynomial time algorithm $A$ whose correctness I can't prove immediately. But say I create a probabilistic version of this algorithm say $A_P$ such that it uses log(n) random bits.  Now if I prove somekind of (exactly what ?) expectation correctness of $A_P$ then does it imply that $A$ was correct?

If the above is not right then I would like if someone can point me to what is the closest correct thing to this!

The statement you state is not the PCP theorem. The PCP theorem is a characterization of NP.

The statement you mention is much easier to prove. It says in effect that a polytime algorithm that uses $O(\log n)$ random bits can be made deterministic while keeping it polytime (given reasonable completeness and soundness properties). The proof is very simple – we can run the algorithm over the $2^{O(\log n)} = n^{O(1)}$ many choices of random bits, check how many times the algorithm accepts, and so determine whether the input belongs to the language.

At most you can think of this as a derandomization procedure – if your algorithm uses only logarithmically many random bits, then you can make it deterministic by "exhaustive search".


How does the strong form of the PCP theorem imply the inapproximability of Max-XORSAT? Theorem 11.4 For any constant $\delta > 0$, every problem in NP has probabilistically checkable proofs of length poly($n$), where the verifier flips $O(\log n)$ coins and looks at three bits of the proof, with completeness $1-\delta$ and soundness $1/2+\delta$.

Moreover, the conditions under which Arthur accepts are extremely simple - namely, if the parity of these three bits is even.
This theorem has powerful consequences for inapproximability. If we write down all the triplets of bits that Arthur could look at, we get a system of linear equations mod 2. If Merlin takes his best shot at a proof, the probability that Arthur will accept is the largest fraction of these equations that can be simultaneously satisfied. Thus even if we know that this fraction is either at least $1-\delta$ or at most $1/2+\delta$, it is NP-hard to tell which. This implies that it is NP-hard to approximate Max-XORSAT within any constant factor better than $1/2$.

First, I don't think it can be as simple as just checking that the parity is even. Merlin could just make Arthur accept anything by handing him a proof of all zeros, and make him reject anything with a proof of all ones. Surely the parity must instead equal some value that Arthur computes along the way.
Further, It's not a priori clear to me that Arthur would select every triplet with equal likelihood. If that wasn't the case, wouldn't it be possible for a no-instance to yield a Max-XORSAT formula where more than $1/2+\delta$ of the clauses can be satisfied even though Arthur accepts with probability less than $1/2+\delta$?
Let's take a degenerate case as an example. Arthur asks Merlin to help him decide whether a given sequence of $n$ bits $\mathbf{b}$ is all ones - $\mathbf{b=1}$ for short.  This problem is trivially in NP. And Arthur clearly doesn't need Merlin's help. But he can go out of his way to use it anyway. Here's what they do:
First Merlin gives Arthur a PCP $\mathbf{x} \in \{0,1\}^n$ (let's assume $n \gg 3$). Then Arthur checks if $\mathbf{b=1}.$ If it is, he checks that $x_1 \oplus x_2 \oplus x_3 = 1$ holds in Merlin's PCP. Otherwise, he checks either $x_1 \oplus x_2 \oplus x_3 = 1$ or $\overline{x_1} \oplus \overline{x_2} \oplus \overline{x_3} = 1$ (note that these can't both be satisfied) with equal probability 0.45. Or with probability 0.1 he checks $x_i \oplus x_j \oplus x_k = 1$ for a uniformly random triplet.
Merlin can thus convince Arthur that $\mathbf{b=1}$ by giving him, for example, the proof consisting of all ones. But if $\mathbf{b\neq1}$ there's no proof that Arthur accepts with probability greater than 0.55. This gives PCP's with completeness $1-\delta$ (indeed we also have completeness 1) and soundness $1/2+\delta$ where $\delta = 0.05$.
Now what's the Max-XORSAT formula corresponding to $\mathbf{b\neq1}$? Well, Arthur could look at any triplet $x_i, x_j, x_k$ as well as $\overline{x_1},\overline{x_2},\overline{x_3}$. So presumably it's the conjunction of all those triplets when XORed together. All but one of these clauses can be satisfied. So the fraction is very close to one. But that's nowhere near the probability that Arthur will actually accept.
PS: We need a PCP tag.

Theorem 11.4 states that for every $\delta > 0$ there is a polytime computable function that on input $\varphi$ outputs a PCP (of a certain form) such that (i) if $\varphi$ is satisfiable then the cost of the PCP (to be defined) is at least $1-\delta$, and (ii) if $\varphi$ is unsatisfiable then the cost of the PCP is at most $1/2+\delta$.

The PCP consists of a distribution over quadruples $(i,j,k,b)$ where $i,j,k$ are indices in the range $1,\ldots,N$, for some $N$ depending polynomially on the size of $\varphi$, and $b \in \{0,1\}$. The value of an assignment $\alpha\colon \{1,\ldots,N\} \to \{0,1\}$ is equal to $\Pr[\alpha(i) \oplus \alpha(j) \oplus \alpha(k) = b]$, and the value of the PCP is the maximum value of an assignment.

(The version in which $b = 0$ always is easy to solve – the zero assignment has value 1. Similarly, when $b = 1$ the one assignment has value 1.)

Furthermore, the distribution is generated using $t = O(\log n)$ random bits. We can think of $i,j,k,b$ as functions of the randomness $r$.

Consider now the MAX-XORSAT instance
$$
\bigwedge_{r \in \{0,1\}^t} (x_{i(r)} \oplus x_{j(r)} \oplus x_{k(r)} = b(r)).
$$
Since $|\{0,1\}^t| = 2^t = 2^{O(\log n)} = \mathit{poly}(n)$, this instance has size polynomial in the size of $\varphi$.

The maximum fraction of constraints satisfied by this MAX-XORSAT instance is exactly the same as the value of the PCP. Hence if $\varphi$ is satisfiable, at least a $1-\delta$ fraction of constraints can be satisfied, whereas if $\varphi$ is unsatisfiable, at most a $1/2+\delta$ fraction can be satisfied.

An approximation algorithm for MAX-XORSAT with ratio strictly better than $1/2$ can distinguish between the two cases (for small enough $\delta$), and so can find out whether $\varphi$ is satisfiable or not. In other words, such an algorithm can be used to solve SAT.


Operations making non-context-free languages regular If $A$ is a non-context free language, is $A^*$ a regular language?
If $A$ is a non-context free language and $B$ is a regular language, is it possible that their concatenation is a regular language?

Let $A$ be $\{a^p\mid p\text{ is prime}\}$. Let $B$ be $\{a\}^*$.

Both $A^*$ and $A\circ B$ are regular. $A^*$ is $\epsilon+aaa^*$ and  $A\circ B$ is $aaa^*$.


CLRS 4.4-3 Height of recursion tree for T(N) = 4T(n/2 +2) + n I'm having a hard time with the following question:

Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = 4T(n/2 + 2) + n$. Use the substitution method to verify your answer.

This is not homework, I'm just practicing myself for an upcoming exam.

The thing I'm having a hard time with is the $n/2 + 2$, what will the height be of this recursion tree?

I came up with the following formula to calculate the cost of each level after a lot of labor:
$2^i n + 2^{i+2}(2^i -1)$ not 100% sure this is correct either.

Any help appreciated, really looking forward to the answer :D
I often make stupid mistakes and I just started doing algo's for my first time.

I'll suggest two methods, but since this is your exercise, you'll have to work out some of the details.  Important: study them both.

Method 1 (the dumb method)

We're going to use guess-and-check.  In other words, we're going to guess a solution to the recurrence $T$, and then we'll check whether our guess is correct.

How do we come up with a reasonable guess?  Well, we could try stuff blindly, but I have a better suggestion.  The reason this recurrence is difficult is because of the nasty $+2$ in $T(n/2+2)$.  So if that's inconvenient, let's throw it away: let's look at what happens with the related recurrence where that isn't present.  In other words, define a new recurrence $U(\cdot)$ by

$$U(n) = 4 U(n/2) + n.$$

Now use your methods to find a solution to $U(n)$ (e.g., recursion tree, etc.).  Finally, use that formulate for $U(n)$ and let's use that as our guess for $T(n)$: let's check whether it also provides an asympotically valid solution to $T(n)$.  If it is, ta-da, you are done!

I call this a "dumb" method because, while it might happen to work on this example, there's no guarantee it will work in every situation.  So that's why it is helpful to know a more powerful method:

Method 2 (transform of variables)

My suggestion is to first apply a change of variables to make that nasty $+2$ go away, then solve the transformed recurrence using standard methods you already know.

Here's an example.  Suppose we define a new recurrence for $S(n)$ by making the definition $S(n) = T(n+3)$.  (This corresponds to the change of variables $n \mapsto n+3$.)  Can you derive a recurrence relation for $S(n)$?  Sure, with some simple manipulation of the definitions of $S$ and $T$, you ought to be able to derive a recurrence of the form

$$S(n) = 4 S(\text{something}) + \text{stuff}.$$

In particular, I think you'll find that the $\text{something}$ has the form $n/2+\text{blah}$.  So, go do it.  Sit down with a pencil and work out the exact recurrence for $S(n)$ (fill in the $\text{something}$ and $\text{stuff}$ parts with their exact expressions).

Now if we were lucky, we'd get a recurrence of the form $S(n) = 4 S(n/2) + \text{stuff}$.  That'd be lucky, because then you could use your standard methods to solve that kind of recurrence (now that the nasty $+2$ is gone).  Unfortunately, when you work this out, you will discover that you were not lucky.  The nasty $+2$ got replaced by some other $+\text{blah}$, which is still nasty (since $\text{blah}\ne 0$).

But don't give up.  It turns out that $S(n)=T(n+3)$ was not lucky.  So try a different definition.  Try replacing the $3$ with some other number.  If you play around with it a bit, I think you will discover that there is another number you can use instead of $3$ that will be lucky: it'll make the recurrence look like

$$S(n) = 4S(n/2) + \text{stuff},$$

and that's a recurrence you should know how to solve (e.g., recursion trees nad such).  Once you find a solution for $S(n)$, you can plug back into the definition $S(n)=T(n+3)$ to get a solution for $T(n)$, and you're good.

This will work.  It takes a little more work, but it is more general, so it is worth knowing.  I suspect it is the method that your instructor wanted you to learn.


"problematic" non-halting inputs for Turing machines Let us start this question out, by defining for a Turing machine, the set of words it doesn't halt on.
Define: $P(M)=\{w\in\Sigma^*|M$ doesn't halt on $w \}$

We know that the $HALT$ problem is $RE\setminus R$ - thus every TM $M$ that computes $HALT$ has a word it doesn't halt on, i.e $P(M)\ne\emptyset$.

From this, arises the (simple)  question:

$Q(1):$ "is a problem undecidable if and only if every TM that computes it has a non empty 'problematic' set $P(M)$?" $ ^{Q\space(1)}$

Moreover, let's note that for the $HALT$ problem we know that given $M$ that computes it, there are infinitely many inputs it will never halt on (I encourage to think why this is so, before proceeding in the post)

So, similarly we might want to ask ourselves the (slightly) harder version of the first question.

$Q(2):$ "is a problem undecidable iff every TM $M$ that computes it has $|P(M)|=\aleph_0$?" $ ^{Q\space(2)}$

Moreover - let's ask an even stronger question:

$Q(3):$ "if $L$ is undecidable, will we still be able to find a finite set of Turing machines $M_1,...,M_n$ that compute $L$ and have $\bigcap_{k\space=\space0}^nP(M_k)$ finite? what about an infinite set of Turing machines that satisfy that?" $ ^{Q\space(3)}$

And our final (and half-open) question will be:

$Q(4):$ "What else can we understand about Turing machines and their problematic sets?"

So, let's start tackling those problems. As a side note, I have arranged the questions such that each question uses the answer of the one before it (and this way, they almost seem too trivial to begin with $:$P).

$A(1):$ is pretty trivial from definition. If $L$ is undecidable then there is no Turing machine that computes it and always halts, thus all Turing machines that compute $L$ have $P(M)\ne\emptyset$.
The other direction is also as simple as this one.

$A(2):$ let's assume $L$ is undecidable. If there was a Turing machine $M$ that computes $L$ and has a finite $P(M)$, then let us build a new machine $\hat M$ such that it will have $P(\hat M)=\emptyset$ as following (on input $w$):

reject if $w \in P(M)$ (this is possible since $P(M)$ is finite)
otherwise, return $M(w)$

this new machine, will halt for every $w\in P(M)$, but since for every $w\notin P(M)$ it will run $M$, and it's guaranteed that it will halt on it (since otherwise it would have been in $P(M)$), we have that the new $\hat M$ always halts, and accepts $L$ - thus contradicting the assumption. The other direction is simply derived from $A(1)$.

$A(3)$: for finite sets of Turing machines, $M_1,...M_n$ we will show that its impossible to have finite $\bigcap_{k\space=\space0}^nP(M_k)$ but undecidable $L$. lets assume towards contradiction this doesn't hold. Just at $A(2)$, we will build $\hat M$ - but now its enough to build it such that $P(\hat M)=\bigcap_{k\space=\space0}^nP(M_k):$

Run $M_1(w), M_2(w), ...,M_n(w)$ in parallel
Accept if any one of them accepted.

Now, it's obvious why $\hat M$ accepts $L$. Let $w\notin P(\hat M)$, then there is some $1\le k\le n$ such that $M_k(w)$ halted, thus $w\notin\bigcap_{k\space=\space0}^nP(M_k)$. let $w\in P(\hat M)$, then it didn't halt on any $M_k$, thus $w\in P(M_k)$ for all $k$. Concluding that $P(\hat M)=\bigcap_{k\space=\space0}^nP(M_k)$ is finite and therefore from $A(2)$ cannot exist.

Regarding infinite sets of Turing machines, this is definitely possible. Just define for each $w\in \Sigma^*$ the machine $M_w$ that accepts $L$ but also halts on $w$ (similarly to the build in $A(2)$). then $w\notin P(M_w)$ therefore $w\notin \bigcap_{\hat w} P(M_\hat w)$ and thus not only that $\bigcap_{\hat w} P(M_\hat w)$ is finite, its also empty.

$A(4):$ let $L$ is undecidable and $M_1,M_2...$ are Turing machines who accept $L$ and their intersection of the "problematic set" is finite. If we look at the function $f:\mathbb{N}\rightarrow\Sigma^*$ defined by $f(k)=\langle M_k\rangle$ , then it is not computable. This follows from $A(2)$ since if that function was computable, we would have been able to create a Turing machine $\hat M$ with $P(\hat M)=\bigcap_k P(M_k)$

Another idea i have started to think about is what happens when we talk about two languages or more, instead of one at a time. Let $M_1$ be a machine for $L_1$ and $M_2$ for $L_2$. then, we can define a machine $M$ for $L_1\bigcap L_2$ or $L_1\bigcup L_2$ with:

$P(M) = P(M_1)\bigcup P(M_2)$ (note this also can prove closure properties in $\mathcal R$)

or if $L_1\Delta L_2$ is finite, then we the problematic sets of machines for the languages are pretty much the same(for every machine $M$ in any one of them we can find machines $M'_1,M'_2$ for the other two languages with the same problematic set)

Although I have yet to write a formal proof of the above. (honestly, I don't have energy to write more proofs like that in this one big post) I still encourage you to try proving that at home!

Finally! I think (but still unsure) we can get similar results (but with more constraints) for time complexity analysis if we define $P(M, t)$ for time-constructible $t(n)\ge log(n)$ as the group of words $M$ doesn't halt on within $t(n)$ steps. In this definition there is the tricky problem of constants, so its harder to show theorems by defining new machines (as they might do just a little bit more constant work that will make some word enter the problematic set, and big-O notation here is somewhat meaningless for different constants)

If you think that something is incorrect, or just want to add more - I will be glad to make changes.


Unbiasing of sequences There is the well-known method of unbiasing of bit sequences due to von Neumann. Are there similar schemes applicable to other sequences, e.g. the result of throwing a normal die?

The following simpler adaptation of von Neumann's trick is more efficient than the one described in HdM's answer. Throw your die twice. If the two answers $x,y$ are different, write $0$ if $x<y$ and $1$ if $x>y$. This way, you get an unbiased bit source. If you are so inclined, you can use this bit source to simulate fair die throws.


Testing all 120 insertion orders is indeed much to much work in order to check out all trees. Moreover, there might be trees that are valid, but which are not found by inserting keys in some order.

A better appraoch would be to designing the trees by level. The number of black nodes on each path is equal, so a RB-tree with five keys can at most have two levels with black nodes: three levels would need seven keys.

It is perhaps helpful to consider a black node together with its red children as one single node with 1,2 or 3 keys (and 2,3 or 4 children). (In that way we get 2-3-4-trees.) Now either (1) the root has 2 keys and three children with each a single child, or (2) the root has 1 key with 2 children with a total of 4 keys. Remember a node with two keys can be represented in two ways as a RB-tree (the red child can be left or right.)

According to the OEIS there are eight such trees. Good luck.


How many zeros should be in front of two's complement model? The Problem
Convert 256 to its 2's complement representation.

My Work

   I know that 256's representation in unsigned binary is 100000000. What I know from working with two's complement model is that the most significant digit represents the sign of the  number. So in this case,   100000000 cannot be 2's complement representation as well because that would mean that the original number, 256 is negative.

   Is there a specified number of zeros I should add to the front of the binary representation? Would it be acceptable to just add one zero to the front, say 0100000000?

Two's complement is a representation of a number. Using different bases, encodings, a number (as a mathematical object) can be represented in many ways.

There is no "specified number of zeros". It is rather than, if you have 10 bits, they can represent 1024 values.
It can be unsigned numbers between 0 and 1023
It can be signed numbers between -512 and +511 if you use two's complement.

"0100000000" is indeed 256 both as unsigned and two's complement signed 10 bits numbers.


Why do relational databases use 2PC for distributed transactions over the likes of Paxos? Paxos is more powerful and in the famous writing "Consensus on Transaction Commit" : http://research.microsoft.com/pubs/64636/tr-2003-96.pdf, Jim Gray and Leslie Lamport describe 2PC as a special case of Paxos.

Why do relational database use 2PC in real world? Also 2PC is not fault tolerant because it uses a single coordinator whose failure can cause the protocol to block.

One of the reasons is the message complexity. For N nodes, 2PC will require 3N to be exchanged whereas Paxos requires 4N. Also, Paxos adds sequence numbers to each message which adds a significant overhead to the overall execution.


I want to pursue a career in computer programming. Where do I start? I am currently finishing up my junior year as a Biochemistry major at a 4-year university. In a year, I will graduate with a B.S. in Biochemistry and way more credit hours than anyone should ever have due to AP classes in high school. To make a long story short, I want to pursue computer programming once I graduate next year. I need to know what to do now, where I should go next. My university does not offer any CS classes, but I am willing to work extracurricularly if it means gaining relevant experience. I'm not completely at square 1, I have some experience with programming, but not nearly enough to compete with a Bachelor's.

1) Do I need a Bachelor's in CS to pursue programming? I have developed and published a handful of websites and iPhone/Android applications over the years, but I never took it on as a full time job. I am conversant in most relevant computer languages, but never as a result of any official classes, just through personal study.

2) What resources are available to me regarding open positions in CS? I have been stuck in my birth state my entire life, and thus have little exposure to the job market outside of a 200-mile radius. I am engaged and plan to move away with my fiancé when we both graduate next year, but I would like to move somewhere that will be conducive to my programming ambitions. Are there any notable cities that are iconic in the CS market?

3) What should I be focusing on now? I would like to finish out my degree program so the past 3 years won't be completely for naught, but what should I be doing in the meantime? Should I pursue some form of internship, should I attempt to strike further out in freelance work, or should I take some sort of online classes?

4) What do employers look for? If I'm looking to make the best first impression, what sort of things should I become conversant in? Is there a core set of languages I should go ahead and start learning?

Honestly I'm just extremely lost and need to know what steps I should take from here. Also, if I can avoid paying for another 4 years of college, that would be great.

You are already making iOS Apps, so you most likely already know at least 1 programming language. You don't need a degree in computer science to be a programmer. You (usually) need a degree in computer science to be a computer scientist.

You should continue programming, as it's the only way you'll get better. If you want to put it on your resume you need to be extremely fluent in at least 1 language and show that you're fluent (you're off to a great start with those iOS apps).

Employers don't look for a CS degree, although it is nice. Most jobs require a bachelors degree, but not in computer science per se.

Putting personal projects on your resume along with an explanation of your ability to write code should be good enough. And trust me, they will be testing your abilities as a programmer from the second you get a callback.

During the first interview, you will most likely be asked to write code on paper with a developer at the company. If you pass that, they might ask you to complete a lengthy exercise to demonstrate your proficiency.

So in my opinion: Keep doing what you're doing. If you want to land a job as a programmer master at least 1 language.


How many RAW dependencies are present in these instructions? What is the number of RAW dependencies in below set of instructions?

I1: R1 = R2 - R3
I2: R2 = R1 + R3
I3: R3 = R1 + R2
I4: R1 = R2 - R2

I can see the following RAW dependencies in it:

  $I_2-I_1\ for\ R_1$ ......... (a)

  $I_3-I_1\ for\ R_1$ ......... (b)

  $I_3-I_2\ for\ R_2$ ......... (c)

  $I_4-I_2\ for\ R_2$ ......... (d)

I think taking (a) and (b) implies that (c) has already been included. So, should this be counted as 4 RAW dependencies or 3 RAW dependencies?

https://en.wikipedia.org/wiki/Hazard_(computer_architecture)#Read_after_write_(RAW)

TL;DR: According to a 5-stage pipeline scenario, there are just two true RAW hazards:

1. I2 to I1 for R1
2. I3 to I2 for R2

Explanation

The answer might depend on the pipeline stages. For the sake of this question, let's consider a basic 5-stage pipeline: Instruction Fetch (IF), Decode (DE), Execute (EX), Memory Op (MEM) and Writeback (WB).

    Instr\Cycle      C1   C2   C3    C4    C5    C6    C7    C8
 ------------------ ---- ---- ----- ----- ----- ----- ----- -----
  I1: R1 = R2 - R3   IF   DE   EX1   MEM   WB1
  I2: R2 = R1 + R3        IF   DE    EX2   MEM   WB2
  I3: R3 = R1 + R2             IF    DE    EX3   MEM   WB3
  I4: R1 = R2 - R2                   IF    DE    EX4   MEM   WB4

At first, it may seem like there are many RAW dependencies in this instruction sequence but let's analyze how the pipeline behaves with this sequence. The above table might indicate the following:

EX2 depends on WB1 (WB1->EX2)
EX3 depends on WB1 (WB1->EX3)
EX3 depends on WB2 (WB2->EX3)
EX4 depends on WB2 (WB2->EX4)

After the first stall in the pipeline by EX2, the scenario changes a bit. WB1->EX2 (1) was a true dependency. But, WB1->EX3 (2) is no more a dependency:

    Instr\Cycle      C1   C2   C3    C4    C5    C6    C7    C8    C9    C10
 ------------------ ---- ---- ----- ----- ----- ----- ----- ----- ----- -----
  I1: R1 = R2 - R3   IF   DE   EX1   MEM   WB1
  I2: R2 = R1 + R3        IF   DE    EX2   EX2   EX2   MEM   WB2
  I3: R3 = R1 + R2             IF    DE    DE    DE    EX3   MEM   WB3
  I4: R1 = R2 - R2                   IF    IF    IF    DE    EX4   MEM   WB4

After the second stall in the pipeline by EX3 (3) (which truly waits for WB2), the scenario changes again. Clearly, WB2->EX4 (4) is revealed to be no more a dependency.

    Instr\Cycle      C1   C2   C3    C4    C5    C6    C7    C8    C9    C10   C11   C12
 ------------------ ---- ---- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
  I1: R1 = R2 - R3   IF   DE   EX1   MEM   WB1
  I2: R2 = R1 + R3        IF   DE    EX2   EX2   EX2   MEM   WB2
  I3: R3 = R1 + R2             IF    DE    DE    DE    EX3   EX3   EX3   MEM   WB3
  I4: R1 = R2 - R2                   IF    IF    IF    DE    DE    DE    EX4   MEM   WB4

Therefore from our original list above, only following true RAW hazards are revealed:

EX2 depends on WB1 (WB1->EX2)
EX3 depends on WB2 (WB2->EX3)


Minimize shipping cost based on weight and price constraints I'm trying to determine the least shipping cost when you have a number of items (each with a weight and a price) that can be combined into the same package. The constraints are as follows:

There is a limit on the max price of the combined package (say $15)
The cost of the package is determined using the following table:

If total weight of package is < 30 grams, cost is 7.5
If total weight of package is >= 30g and <80g, cost is 7.5 + (weight - 30)x0.075
If total weight of package is >= 80g, cost is 7.5 + (weight - 30)x0.055

There is no limitation on the number of packages these items can be combined into as long they remain under the total price threshold.

I looked at the knapsack problem, but there are 2 major differences between the knapsack problem and my problem:

One is that we are not maximizing the weight or price of the items combined, instead we want to minimize a calculated variable that can only be determined after the combination.
Also, there isn't a direct correlation between weight and shipping cost.

Since the objective function is piecewise linear, the problem can be formulated as an integer linear program.

Given items with prizes $p_1,\ldots,p_n$ and weights $w_1,\ldots,w_n$, define binary variables $x_i$ for $i\in[n]$ where $x_i=1$ if item $i$ selected. For each of the three segments a binary variable $\delta_k$ selects the active segment, and the convex combination of $(\lambda_1,\lambda_2)$, $(\lambda_2,\lambda_3)$, or $(\lambda_4,\lambda_5)$ defines the point in the first, second, or third segment, respectively. Note that $\lambda_3=1$ and $\lambda_4=1$ are different, since your objective function is not continuous at $80$. Auxiliary variables $w$ and $c$ hold the total weight and cost. Finally $W=\sum_{i\in[n]} w_i$ is an upper bound on the maximum weight.

With this you can
\begin{align}
\text{min.}\quad & c,\\
\text{s.t.}\quad & \delta_1 + \delta_2 + \delta_3 = 1,\\
    & \lambda_1+\lambda_2 = \delta_1,\\
    & \lambda_2+\lambda_3 = \delta_2,\\
    & \lambda_4+\lambda_5 = \delta_3,\\
    & w = 30\lambda_2+80(\lambda_3+\lambda_4)+W\lambda_5,\\
    & c = 7.5\lambda_1+7.5\lambda_2+11.25\lambda_3+10.25\lambda_4+(7.5+0.055(W-30))\lambda_5,\\
    & \sum_{i\in[n]} p_ix_i \leq 15,\\
    & \sum_{i\in[n]} w_ix_i = w,\\
    & x_i\in\{0,1\}, i\in[n],\\
    & \delta_1,\delta_2,\delta_3\in\{0,1\},\\
    & \lambda_1,\lambda_2,\lambda_3,\lambda_4,\lambda_5\geq 0,\\
    & w,c\geq 0.
\end{align}

For, say, about 100 items I guess a standard solver can find the optimal solution in a few minutes.

(From your question it is not clear me if you want to select a subset of the items that can be sent at optimal cost, or minimize the total cost for all packages to send all items. For the latter you can extend the model by using variables $x_{ij}$ that indicate if item $i$ goes to the $j$th package, use similar constraints to define the cost for each package, and then minimize the total cost.)


How can you define the notion of "state" using only a type theory language? The notion of state I'm referring to is the one described in this wikipedia page : https://en.m.wikipedia.org/wiki/State_(computer_science)

Which defines it in this way:
 "a program is described as stateful if it is         designed to remember preceding events or user interactions; [1] the remembered information is called the state of the system."

My question is: Does there exist one or more formal definitions/descriptions that correspond to this notion of "state",  in a formal system of Type theory (might be system F , simply typed lambda calculus or any other)

I am not sure what your question exactly covers. But to have a more formal definition of "State" it could be useful to look at the State Monad in Haskell. Haskell is a functional programming language which operates different compared to a imperative programming language (like Java or C).


Interval Scheduling problem with more than 1 machine There are 2 machines.
Each task either requires 1 or 2 machines to run (ie, a 1-machine task can run in parallel with another 1-machine task but a 2-machine task occupies both machine
The list of n tasks are given in [start time, end time], both of which are on top of hours. If we were to order the tasks by non decreasing end time the maximum would be D, but the list given is not sorted.
There is no value difference (1 machine and 2 machine tasks are considered same value). Just schedule as many tasks as possible. Want to find an algorithm that runs within O(nD^2) time
I'm considering DP but can't really get my head clear on how to approach the question. Any suggestion would be helpful.

You may want to consider a solution with dp(i, j, k) where i represents the x that machine 1 is at, j represents the x that machine 2 is one, and k represents the index of the task you're considering
The state transition in this case would be O(1) because you either take the task or not, for which you can increment/decrement i/j accordingly.
I'm not sure what D and n are but if D refers to the amount of time allotted for machine 1 and 2 and n is the number of tasks, then I believe this could be the solution you're looking for
Note that "x" refers to time. Also, this solution would work if the tasks were assigned a value
Let me know if you want an implementation of this


Algorithm to find "truncatable words"? My son who is just learning to read loves the concept of hiding one letter of a word with his finger and asking what the rest of the word spells. His favorite is turning "her" into "he" and "then" into "the."

As he's starting to learn bigger words I want to find some words for him that are "truncatable," similar to the concept of a truncatable prime. These would be dictionary words that are also dictionary words when a character is removed from either the left or the right side. A properly "truncatable" word would continue to be a word down to 1 character, but I would be really only looking for those that are truncatable down to three letters:

 Browser
 Browse
 Brows
 Rows
 Row

What is the best algorithm to do this? My initial naive approaches are proving quite horribly inefficient for the dictionary file that I am using. I am currently literally testing every word in the dictionary, recursively, and the running time and space are intractable and the methodology ends up testing each word many times.

Is there an efficient memoized or otherwise optimized way of finding truncatable words?

Edit: Thank you to https://cs.stackexchange.com/users/755/d-w who provided guidance, this is the code I ended up coming up with which works:

# find list of truncatable words in English
# truncatable words are those where a word
# can be dropped from the beginning or end
# to form a new valid word, all the way down
# to three letters or fewer!

def main():
    # Find the truncatable words

    # read dictionary into a list
    f = open("english3.txt","r")
    wordlist = []
    for line in f:
        wordlist.append(line.strip().lower())

    # sort by length

    wordlist2=sorted(wordlist,key=len)
    max_word_length = len(wordlist2[-1])

    # set up list of dictionaries for truncatable words
    Truncatables = []
    for filler in range (max_word_length+1):
        Truncatables.append({})

    # iterate through dictionary and test for truncatability
    for word in wordlist2:
        if len(word)<=3:
            Truncatables[len(word)][word]='default'
        else:
            front = word[1:] in Truncatables[len(word)-1]
            back = word[:-1] in Truncatables[len(word)-1]
            if front and back:
                Truncatables[len(word)][word]='both'
            elif front:
                Truncatables[len(word)][word]='front'
            elif back:
                Truncatables[len(word)][word]='back'
            else:
                pass
    print(Truncatables)

    # Define a function that recursively prints out a truncatable chain

    def printTruncatable(word):
        if word in Truncatables[len(word)] and word in wordlist2:
            print(word," ",end="")
        TruncType = Truncatables[len(word)][word]
        if TruncType == "back" or TruncType == "both":
            printTruncatable(word[:-1])
        elif TruncType == "front":
            printTruncatable(word[1:])
        elif TruncType == "default":
            print("\n")
        else:
            print("ERROR")

    # print the top truncatables
    for wordlength in range(max_word_length,7,-1):
        for key in Truncatables[wordlength]:
            print(wordlength,": ", end="")
            printTruncatable(key)

if __name__ == "__main__" :
    main()

Here is a simple implementation strategy.

Find all three-letter truncatable words.  Every three-letter word is truncatable, so this is a linear scan through the dictionary to find the three-letter words.  Store them in a hashtable.

Find all four-letter truncatable words.  You can check whether a four-letter word wxyz is truncatable by checking whether wxy is a truncatable word; the latter can be checked by looking it up in the previous hashtable.  So, this can be done with a linear scan through the dictionary.  Store all four-letter truncatable words in a hashtable.

Find all five-letter truncatable words, by a linear scan plus a lookup in the hashtable for four-letter truncatable words.  Note that given a word vwxyz, it suffices to check whether vwxy is truncatable (you don't need to check vwx).

Find all six-letter truncatable words.

And so on.  Finish when you've exhausted the length of words in the dictionary.


Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$ Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$.
The book from which this example is, falsely claims that $T(n) = O(n)$ by guessing $T(n) \leq cn$ and then arguing

$\qquad \begin{align*} T(n) & \leq 2(c \lfloor n/2 \rfloor ) + n \\ &\leq cn +n \\ &=O(n) \quad \quad \quad \longleftarrow \text{ wrong!!} \end{align*}$

since $c$ is constant.The error is that we have not proved the exact form of the inductive hypothesis.

Above I have exactly quoted what the book says. Now my question is why cannot we write $cn+n=dn$ where $d=c+1$ and now we have $T(n) \leq dn$ and hence $T(n) = O(n)$?

Note:

The correct answer is $T(n) =O(n \log n).$
The book I am referring here is Introduction to algorithms by Cormen et al., page 86, 3rd edition.

The authors give the answer:

  The error is that we have not proved the exact form of the inductive hypothesis, that is, that $T(n) \leq cn$.

Granted, that is hard to understand if you are not used to do inductions (right), because they do not do the induction explicitly/rigorously. In short: you need to have one constant $c$ for all $n$, but this (un)proof constructs many (one per $n$).

In long, remember what $T(n) \in O(n)$ means:

$\qquad \displaystyle \exists c \in \mathbb{N}.\, \exists n_0 \in \mathbb{N}.\, \forall n \geq n_0.\, T(n) \leq cn$

or, equivalently,

$\qquad \displaystyle \exists c \in \mathbb{N}.\, \forall n \in \mathbb{N} T(n) \leq cn$.

The second form works better for an induction as you know the anchor. So you need one constant $c$ that provides an upper bound for all $n$.

Let's inspect what the induction does:

Induction anchor: The anchor of $T$ is not explicitly given, but it's constant, so we find a suitable $c$.
Induction hypothesis: There is some $c$ so that $T(k) \leq cn$ for all $k\leq n$, for some arbitrary but fixed  $n$.
Inductive step: as shown in the question, construct $d > c$ so that $T(n+1) \leq dn$.

So, in effect, we construct a new constant for every $n$. That does not fit the definition of $O$ at all! And, worse, it is completely meaningless: every function can be "bounded" by any other function if you can adjust the factor with $n$.

Regarding the induction proof, $c$ has to be part of the claim (and it is, hidden in the $O$), that is bound "outside" of the induction. Then, the same $c$ shows up in anchor, hypothesis and step. See the last part of this answer for an example.


Color Filler Algorithm Is there an algorithm that fills the area outside the edges?

e.g.:

From this

to this

Assuming for simplicity that the edges don't touch the image boundary (you can always guarantee that by adding a pixel-wide "frame"), you can simply run flood fill from an arbitrary point on the image boundary.


how to find upper bound and lower bound of quadratic equation I am relatively new to algorithms, I wrote one pattern matching algorithm and its running time is $O(n^2)$, I tried it by step count method, direct method and also the constant method which all yields same results. Anyhow now I am writing the upper and lower bound for that, the equation which I get is

$$20n^2+11n+1$$
I need to find the

$$c_1n^2 \leq 20n^2+11n+1 \leq c_2n^2$$

Here I am stuck and needs some assistance, I have gone through a lot of examples, books, and youtube videos, but no one has any method to solve it instead of assumption and different ways. Any help is much appreciated.

EDIT
Graph for the equation

Since $n \geq 1$ (since $n$ is the input length), we have
$$
20n^2 \leq 20n^2 + 11n + 1 \leq (20+11+1)n^2 = 32n^2.
$$
Put differently, for all $n \geq 1$, the function $f(n) = 20n^2 + 11n + 1$ is bounded from below by $20n^2$ and from above by $32n^2$. This shows that $f(n) = \Theta(n^2)$.

Note also that when $n$ is large, $f(n)$ gets very close to $20n^2$. Indeed,
$$
1 \leq \frac{f(n)}{20n^2} \leq 1 + O\left(\frac{1}{n}\right).
$$


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

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

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


Is it possible to detect cats from dogs in image with single layer perceptron? I want to make a simple application that input is an image and output must be 0 if image is dog and 1 if image is cat. Is it possible to detect cats from dogs in image with single layer perceptron?

No, that's just not possible.

  Although the perceptron initially seemed promising, it was quickly proved that perceptrons could not be trained to recognise many classes of patterns.

Check the Wikipedia article on the subject.


show that in every infinite computably enumerable set, there exists an infinite decidable set I came across this problem: Show that in every infinite computably enumerable set, there exists an infinite decidable set.

As an attempt to solve the problem, I could only think of a proof by construction. Without loss of generality, let the alphabet be $\Sigma=\{0,1\}$. The construction goes as follows, suppose that $TM$ $M$ recognizes an infinite computably enumerable set $L$, we can form a decidable language $D \subseteq L$ as follows:

  1) lexicographically enumerate all input words $w$ in $\Sigma^*$ and repeatedly perform steps $a-b:$

    a) at the $k$th step, run $M$ on input words $\{w_0,w_1,...,w_k\}$ for $k$ steps, where words $\{w_0,w_1,...,w_k\}$ are lexicographically ordered

    b) if $M$ accepts an input word $w \in \{w_0,w_1,...,w_k\}$ from step 2, include $w$ in a temporary language $D_{temp}$

  2) partition the words in $D_{temp}$ into two, those starting with $0$ are $\in D$, while those starting with $1$ are $\not \in D$, along with all other words $\Sigma^* - D_{temp}$.

Step (1) does not loop in a word $w$ since each run of step (1) is limited for a finite number of $k$ steps. Is this construction okay ? Or did I miss something ...

Here is one possible approach. Since $L$ is c.e., there is some enumerator that outputs a list of the word in $L$: $w_1,w_2,\ldots$.

Let $D$ consist of all words $w_i$ which are longer than all words appearing before them. I claim that $D$ is infinite. If not, let $w_m$ be the last word in $D$. Then all other words have length at most $|w_m|$. However, this contradicts the infinitude of $L$.

Furthermore, $D$ is decidable. Given a word $w$, run the enumerator for $L$, and halt whenever one of the following events happen:

If $w_i = w$, output Yes.
If $|w_i| > |w|$, output No.

Since $L$ is infinite, this algorithm will eventually stop.


Mistake in Karp's paper on NP-Complete problems? I read on a blog that there are mistakes in Karp's paper where he proved that 0-1 programming is NP-Complete, but I couldn't find it, can anyone explain? And I doubt that there are also mistakes where he proved Steiner Tree Problem is NP-Compelete but not sure.

The blog post a little old and I thought asking the writer of the blog may not receive answer quickly enough. I didn't find any referrence in other places so I thought this question may worth asking.

To cite the blog post:

  For arguments sake, lets say that in Karp's classic paper Reducibility Among Combinatorial Problems, where he proves 21 problems NP-compete, he made a mistake on 0-1 programming.

That is, the blog author does not state that there is a mistake. It is just a gedankenexperiment.

That is, of course, not to say that there is none.


'simple' algorithm that can predict disk usage or 'time to be full' Let say I have time series of disk usage of last 30 days..
Given this information and with the assumption that the disk usage 'pattern' isn't changing dramatically over time, what would be a naive/simple algorithm to predict when is disk going to be full?

I'd try fitting a linear model (i.e., assume new data arrives at a constant rate) or an exponential one (i.e., new data is proportional to what is already there), and see which one is better.


Reconciling NP and the decision problem So I've seen that most NP-Complete problems seem to take the form of decision problems - problems which require only a yes/no answer. However, how can this be reconciled with the requirement that the solution of an NP problem can be checked in polynomial time?

For example, for a graph G, the max cut decision problem: "Does a cut of size at least k exist?" is NP-Complete. However, given a particular solution, "yes", the problem of checking that the solution is "yes" would require you to find a max cut of size k, so how can this be in NP?

By definition, all NP-complete problems are decision problems. In fact, the category of NP-completeness only applies to decision problems. Any other kind of problem cannot be NP-complete any more than an apple.

A decision problem A is in NP if there is an integer $m$ and a decision problem B, which can be decided in polynomial time, such that:

If $x \in A$ then there exists $y$ of size at most $m|x|^m$ (here $|x|$ is the size of $x$ in bits) such that $\langle x,y \rangle \in B$.
If $x \notin A$ then for every $y$ of size at most $m|x|^m$ it holds that $\langle x,y \rangle \notin B$.

The string $y$ is called a witness.

This definition is a bit abstract, so let me explain it using your example, the Max Cut problem. The Max Cut problem, as a set, consists of all pairs $\langle G,k \rangle$ such that $G$ is a graph containing a cut which cuts at least $k$ edges. The desired witness $y$ is a cut which cuts at least $k$ edges. The decision problem B consists of all pairs $\langle \langle G,k \rangle, C \rangle$ in which $G$ is a graph and $C$ is a cut in $G$ which cuts at least $k$ edges. The problem Q can be decided in polynomial time – that is, given a graph $G$, a cut $C$ in $G$, and an integer $k$, it is easy to check whether $C$ cuts at least $k$ edges. The size of $C$ is also polynomial in the size of $\langle G,k \rangle$.

As jmite explains in the other answer, this definition is equivalent to the more usual one: NP consists of all decision problems which can be decided using non-deterministic polynomial time machines. Let me sketch why the two definitions are equivalent.

Suppose first that A is in NP according to the definition stated above. The non-deterministic polynomial time machine deciding A guesses the witness $y$ and then verifies it (using the polynomial time algorithm for B), accepting if the verification succeeded.

For the other direction, the sequence of non-deterministic choices functions as the witness $y$. We can verify that a specific sequence leads to acceptance by running the non-deterministic polynomial time machine using $y$ as its choices.


Uniform generation of random bipartite bi-regular graphs? I want an algorithm that takes the following

Input: $M,N,k,d$ positive integers such that $kM = dN$.

and produces the following

Output: Random bipartite graph, with $M$ vertices all of degree $k$ on one partition, and $N$ vertices all of degree $d$ on the other partition. No loops allowed. The output should be uniformly distributed among all possible graphs.

Does an algorithm like this exist? If so please provide a reference.

The problem of generating random $d$-regular graphs uniformly at random has been extensively studied. Some of the proposed algorithms are quite sophisticated. In general, the problem becomes more difficult as $d$ grows as a function of $n$. To the best of my knowledge, the problem is still open for $d = \omega\left(\sqrt{n}\right)$.
However, if one assumes that $d$ is a constant, then there is a simple and efficient algorithm called the configuration model:
https://en.wikipedia.org/wiki/Configuration_model
It can be easily adapted to the case of biregular graphs with $M$ vertices of degree $k$ on the left side, and $N$ vertices of degree $d$ on the right side. Of course, for this to be possible at all we need $Mk=Nd$.
The algorithm is as follows:

Assign each vertex on the left side $k$ ``half-edges", and each vertex on the right $d$ half-edges.

Choose a uniformly random perfect matching of size $Mk$ matching all of the half-edges on the left side to the half-edges on the right side.

This tells you which vertices to connect to which, but there may be double edges. Repeat the above procedure until there are no double edges.

It is pretty easy to see that the resulting distribution is uniform by counting the number of perfect matching that can yield a given graph. It is harder to analyze the probability that there are no double edges, which is critical if we want to bound the expected runtime. However, it turns out that for constant $k$ and $d$, the probability that there are no double edges is a constant independent of $n$, and so we only need to repeat the algorithm $O(1)$ times.


Intersection with a finite set If we have a language $F$ and a regular language $D$ (a finite set) then can we say anything about the intersection of $D$ and $F$? Will the intersection of the languages be finite or regular?

This question arises from another question which says

Show that if $L$ is not a CFL and $F$ is finite then $L - F$ is not a CFL.

Now $L = (L - F) ∪ ( L ∩ F)$.

Now if I am able to prove that $L ∩ F$ is finite or regular than I can arrive at a contradiction as follows:

If $L ∩ F$ is finite or regular then union with $L-F$ will be a CFL, therefore $L$ will be a CFL, which is a contradiction.

But my problem is assuming anything about $L ∩ F$.

What will be the properties of this intersection?

There is no need to consider the intersection $L \cap F$. If $F$ is finite, then so is $L \cap F$, but that is not a useful fact here.

Insteed, one should proceed by contradiction. Suppose $L \setminus F$ were a context-free language. Then there exists a context-free grammar $G_1 = (V_1,\Sigma,R_1,S_1)$ such that $L(G_1) = L \setminus F$. But since $F$ is finite, then $F$ is trivially a context-free language. Let $G_2 = (V_2,\Sigma,R_2,S_2)$ be a context-free grammar such that $L(G_2) = F$.

But then $G = (V,\Sigma,R,S)$ where $S \notin V_1 \cup V_2$ and

$$V = V_1 \cup V_2 \cup \{ S \}$$
$$R = R_1 \cup R_2 \cup \{ S \rightarrow S_1, S \rightarrow S_2 \}$$

is a context-free grammar such that $L(G) = L$. This is a contradiction.


Converting a number to 16-bit Floating Point Format I want to convert the number -29.375 to IEEE 745 16-bit floating point format. Here is my solution:

The format of the floating point number is:
     1 sign bit
     unbiased exponent in 4 bits plus a sign bit
     10 bits for the mantissa plus the explicit 1

First, I realize that 29.375 = 29 + 3/8.
Then realize that:
     29 = 16 +13 = 16 + 8 + 5 = 16 + 8 + 4 + 1
     1 1101.011 = 1.1101 0110 * 2^3

This gives us:
mantissa is: 1101 011000
sign: 1
exp: 00011

Hence in 16 bits, we have:
    1000111101011000

Do I have this right? I was hoping that there would be a calculator on the web that I could use but I could not find one. They were all at least 32-bits.

First of all, the IEEE 745 16-bit format has:

1 bit for the sign.
5 bits (not 4) for the biased exponent. The bias is $15$.
10 bits for the mantissa. The leading $1$ is implicit (not explicit).

The calculation is incorrect since $(29.375)_2 = (11101.011)_2 = (1.1101011)_2 \cdot 2^4$ (and not $2^3$).

Then:

The sign bit is $1$ because the number is negative.
The unbiased exponent is $(4)_{10} = (100)_{2}$ and therefore the biased exponent is $(19)_{10} = (10011)_2$.
The mantissa, without the implicit leading $1$ and padded to 10 bits with trailing zeros, is  $(1101011000)_2$.

Then the final $16$-bit number is: $11001101011000$.


Finding a boolean submatrix isomorphic to a specific fixed set of other boolean matrices Given a matrix $M$ of certain size $h\times w$, where $h\leq w$, for example $5\times 6$, are also given the following set $B$ of additional all-ones matrices, that I like to call target (b)oxes.
$$
\begin{matrix}
    Boxes: &
    \begin{bmatrix} % 2 x 5
      1 & 1 & 1 & 1 & 1\\
      1 & 1 & 1 & 1 & 1
    \end{bmatrix}
    &
    \begin{bmatrix} % 3 x 4
      1 & 1 & 1 & 1\\
      1 & 1 & 1 & 1\\
      1 & 1 & 1 & 1
    \end{bmatrix}
    &
    \begin{bmatrix} % 4 x 3
      1 & 1 & 1\\
      1 & 1 & 1\\
      1 & 1 & 1\\
      1 & 1 & 1
    \end{bmatrix}
    &
    \begin{bmatrix} % 5 x 2
      1 & 1\\
      1 & 1\\
      1 & 1\\
      1 & 1\\
      1 & 1
    \end{bmatrix}\\
    Sizes: & 2 \times w - 1 & 3 \times w - 2 & 4\times w - 3 & 5\times w - 4
\end{matrix}
$$
As you can see, these specific boxes have sizes starting from $2\times w - 1$ up to $h\times w - h + 1$.
The problem is finding a submatrix of $M$ that is isomorphic with any of the boxes in $B$. In other words, swapping rows between them, and/or columns between them so that any of the boxes of $B$ can be placed, for example, in the top left corner of $M$.
If there is more than one solution, the box of maximal height must be choosen, and if there's more than one solution of maximal height, then the one with maximal height and width.
The problem has the following properties:

$2 \leq h \leq w$.
Each row of $M$ has at least one $0$.
Deduced from the way $B$ is generated, for each $b\in B$ of size $b_h\times b_w$, it happens that $b_h + b_w - 1 = w$.

Is there a way of solving this problem in polynomial time? Can any technique from lineal algebra or numerical characterization of matrices help to the problem?

The problem is NP-hard; it is at least as hard as the biclique problem.
If you can solve the problem for a single shaped box, you can solve for all boxes by just iterating over all the boxes.  So your problem reduces to:

Given a matrix $M$ and integers $h', w'$, find a $h'\times w'$ submatrix of $M$ that is all ones, or report that none exists.

This problem is NP-hard.  In particular, if we take any undirected bipartite graph $G$ with adjacency matrix $M$, then $M$ has an all-ones $k \times k$ submatrix if and only if $G$ has a $k$-biclique.  Testing for the presence of a $k$-biclique is NP-hard, so your problem must be, too.


What is the difference between "for infinitely many n" and "for all n"? I have read some complexity papers in which "for infinitely many input sizes" is used.

What is the difference in the computational complexity context between "for infinitely many input sizes" and "for all input sizes"?

"for infinitely many input sizes $n$, $P(n)$ holds" means there are input sizes $n_1$, $n_2$, $\ldots$, (infinitely many) such that $P(n_i)$ holds for all $i$. In other words, for every integer $k$, there is an input length $n \geq k$ such that $P(n)$ holds.

In contrast, "for all input sizes, $P(n)$ holds" means that for every input size $n$, $P(n)$ holds.

Typically, "for all input sizes, $P$ holds" and "for almost every input size, $P$ holds" are used interchangeably, although the latter technically means that there is a $k$ such that for all input sizes $n \geq k$, $P$ holds. (Note that the negation of "for infinitely many input sizes, $P$ holds" is "for almost every input size, $\neg P$ holds.") This is generally because in the models of computation being considered, constant factors don't matter, so from an "almost every input size" statement you can generally hardcode the solutions for all inputs of length less than $k$ in your model, and get a "for all input sizes" statement.


Are if statements unnecessary if a program is represented as an explicit state machine? This question occurred to me some time ago when I was thinking about whether or not if statements are fundamental in computation.

Consider a program that manages a single bank account (for the sake of simplicity). The bank account could be defined as something like

Account
{
    int balance; // current amount of Money

    boolean withdraw(int n)
    {
       if (balance >= n)
       {
           balance = balance -n;
           return true;
       }
       else
           return false;
    }

    void deposit(int n)
    {
       amount = amount + n;
    }
}

Since the program has no way to known in which state it currently is unless it performs validations using if statements, as in the withdraw operation, if statements are unavoidable.

However, over the course of time, the program will pass through a finite set of states that can be known beforehand. In this particular case, a state is defined solely by the value of the balance variable, hence we would have states: {balance = 0 , balance = 1, balance = 2...}.

If we assign each state a number, say state {0,1,2,....} with a 1-1 correspondence to the above set of states, and assign to each operation a number identifier as well (say deposit = 0 and withdraw = 1), we could model the program as an explicit transition between states and therefore remove every if statement from the code.

Consider that state = 0 is the state where balance = 0 and we want to perform a deposit of 50 dollars, if we coded every single possible execution of the deposit function, we could just define the deposit function as

void deposit (int n)
{
   deposit[state][n]; // índex deposit instance for state = 0, amount = n;
}

deposit[][] would be a matrix of pointers for a set of functions that represent each possible execution of deposit, like

deposit[0][0] -> balance = balance + 0; state = 0;
deposit[0][1] -> balance = balance + 1; state = 1;

....

In the case of withdrawal, it would be like:

boolean withdraw (int n)
{
    // índex withdraw instance for the current state and amount=n
    return withdraw[state][n];
}

withdraw[][] would be a matrix of pointers for a set of functions that represent each possible execution of withdraw, like:

deposit[0][100] -> return false; state = state;
...
deposit[200][100] -> balance = balance - 100; return true; state = 100;

In this situation, the program the managers the single bank account can be written without using a single if statement!

As a consequence however, we have to use A LOT more memory, which may make the solution unreasonable. Also one may put the question of how did we fill the deposit[][] and withdraw[][] matrices? By hand? It somehow implies that a previous computation that used ifs as necessary to determine and possible states and transitions.

All in all, are ifs fundamental or does my example prove that they aren't? If they are, can you provide me an example where this does not work? If they are not, why dont we use solutions like these more often?

Is there some law of computation which states that if statements are unavoidable?

Literal if statements are not fundamental. As you've shown, it's possible to remove them by writing your program as a state machine, though at the gigantic cost of having to have a different version of the widthdraw() function for every possible starting balance and withdrawal amount. You can also avoid literal if statements by replacing

if (condition) {
    foo
} else {
    bar
}

with

b1 := condition
b2 := not(b1)
while (b1) {
    foo
    b1 := false
}
while (b2) {
    bar
    b2 := false
}

On the other hand, doing so has no clear advantages and many disadvantages. The gigantic-table-of-functions approach leads to huge redundancy, is very hard to maintain and is very hard for compilers and CPUs to optimize.  If you're lucky, the while loop hack might compile to the same code as the simple code with if statements but it's much harder to read and much more prone to programmers mistakenly thinking they can optimize it.

At a fundamental level, some form of conditional execution is necessary. If you have no kind of conditional statement at all, then you can only perform a class of very limited programs called "straight-line programs". These are, perhaps surprisingly, useful as a model of computation because they have a fairly simple correspondence with circuits: they correspond to the simplest notion of algorithm, i.e., take your input data and perform a fixed sequence of operations on it. For example, when you compute the length of a 2D vector, you're using a straight-line program: square the $x$-coordinate, square the $y$-coordinate, add the two squares, take the square root (at least, assuming that all those arithmetic operations, including square root, are taken as being built in to your langauge).


Produce all unordered unique combinations of N-sized subsets of an m·N-sized set Say there is a set of m·N named elements. How to produce all the (unordered) combinations of N-sized subsets?
For example, m=2 and N=2, the elements are called A, B, C and D. There will be 3 combinations: AB+CD, AC+BD and AD+BC.
For m=2 and N=3 there will be 10 combinations. In general, it will be:
$$\frac{(mN)!}{(N!)^m\cdot m!}$$
(thanks to Ross Millikan)
How to approach creating an algorithm that produces / iterates over the whole set of combinations?

Knuth wrote a chapter on this, as part of the new volume 4 of his Art of Computer Programming.
The simplest algorithm uses the following recursion to generate all combinations of length $m$ of a set $x_1,\ldots,x_n$:

If $m = 0$ then output the empty set.
Otherwise, for each $m \leq i \leq n$, generate all combinations of length $m-1$ of $x_1,\ldots,x_{i-1}$, and add $x_i$ to all of them.


Finding a way out of a polygon There is a simply-connected polygon $C$. It contains $n$ pairwise-interior-disjoint simply-connected polygons, $D_1,\dots,D_n$:

The goal is to select one of the polygons, say $D_i$, and attach to it a polygon $E_i$ such that:

$D_i\cup E_i$ is still simply-connected.
$E_i$ is interior-disjoint from all other polygons $D_i$.
$D_i\cup E_i$ is connected with the exterior of $C$:

Is there an algorithm, preferably published, that solves this problem in time polynomial in the representation of the problem (e.g. total number of vertices of all polygons)?

Basically this is shortest path problem in polygon with holes. There is no constraint in taking $E_i$ as a path of negligible width.

If you just want to connect internal holes to outside boundary without caring about the path length, then just take any point on the boundary of interior hole and calculate a path to any point on the outer boundary. I don't know your application, but probably you are looking for minimum link rather than minimum euclidean distance, in that case minimum link path would be better.

References:
1) S. K. Ghosh and D. M. Mount. An output-sensitive algorithm for computing visibility graphs. SIAM Journal on Computing archive
Volume 20 Issue 5, Oct. 1991
Pages 888-910   (for shortest paths among obstacles)
2) J. Hershberger and S. Suri. Efficient computation of Euclidean shortest paths in the plane. In Proc. 34th Annu. IEEE Sympos. 1993.
3) Joseph S. B. Mitchell, Günter Rote, and Gerhard Woeginger: Minimum-link paths among obstacles in the plane. Algorithmica 8 (1992), 431-459.

However, I should warn you, all the implementations for shortest path, or shortest link path use triangulation for which the optimal algorithm is not very practical. You can however use any sub-optimal algorithm which may be more efficient for your purpose.

The above algorithms are all polynomial in input size.


Efficient algorithm for detecting overlaps in time intervals Let's say I am building a time clock app. The employee can log into the interface and then enter time for multiple projects so that we can generate reports for billing as well as payroll.

A table in the database will record the time-in and time-out for each project as a row. A user should be able to sign out and back into the same project multiple times throughout the day, and also can enter time out of order (e.g. sign into Project X at 9:00 AM to 2:00 PM, then into Project Y from 7:00 AM to 8:30 AM).

So let's say my table looks like this:

Project   | Time In | Time Out
----------|---------|---------
Project X | 9.25    | 14.25
Project Y | 7.00    | 8.50

(I am representing the data as a decimal number of hours simply because it's easy to read in the example; the data is actually MySQL TIMESTAMPs.)

Assuming that the data is not in any particular order, I am wondering what would be the simplest and/or most optimized way to validate that the next entry does not conflict with the existing time in such a way that the employee is signed into two projects simultaneously.

e.g. If the user tries to sign in at 12:00 PM or at 7:30 AM, it throws an error because the user was already working on Project X at noon and Project Y at 7:30.

I know I could do this by getting all the time clock data and then detecting if time_in <= input[time] <= time_out, but I'm wondering if there's a cleaner method to accomplish this task.

select * from table where end_time > 12.00PM order by end_time

fetch single row, and check if start_time < 12.00PM.


Recursion to DP Solution There's a problem in Kleinberg & Tardos's Algorithm Design (Chapter 6, Question 4) where you are running a lightweight consulting business that has two offices: NYC and SF. In month $i$, you'll incur an operating cost of $N(i)$ if you run the business out of NY; you'll incur an operating cost of $S(i)$ if you run the business out of SF. There is a moving cost $M$ if you decide to switch offices. The goal is to minimize total cost. According to the solutions, a DP solution would look like this:

$$
OPT(i, N) = N(i) + \min(OPT(i-1, N), OPT(i-1, S) + M), \\
OPT(i, S) = S(i) + \min(OPT(i-1, S), OPT(i-1, N) + M).
$$

I'm trying to figure out how one can use recursion as opposed to DP to solve this solution. My understanding is that recursion works from top to bottom and DP works bottom up. I'm just having trouble actually figuring out a viable top to bottom recursive algorithm would look like in this case.

The recursive solution is to use the recurrence directly.

It corresponds to the following algorithm:

Function OPT(i, site):
    If i = 0, return 0
    If i > 0 and site = N, return N(i) + min(OPT(i-1, N), OPT(i-1, S) + M)
    If i > 0 and site = S, return S(i) + min(OPT(i-1, S), OPT(i-1, N) + M)

If you run this algorithm using memoization (not recomputing the value for the same input), then you get essentially the dynamic programming solution.

One way to implement this kind of approach is like so:

Function OPTm(i, site):
    If i = 0, return 0
    If (i, site) in Database, return Database(i, site)
    If site = N, answer = N(i) + min(OPTm(i-1, N), OPTm(i-1, S) + M)
    If site = S, answer = S(i) + min(OPTm(i-1, S), OPTm(i-1, N) + M)
    Database(i, site) = answer
    return answer


Four functions problem This is not from online contest
Hi guys, a friend of mine recently give me this problem that I couldn't figure out an effective way to solve it.

Four functions
You are given four functions
$$
\begin{align}
A(x)&=\text{Number of }i\text{ where }1\leq i\leq x\text{ and }\gcd(i,x)=1\\
B(x)&=\sum_{d|x}A(d)\\
C(x)&=\text{Sum of exponents of each prime in the prime factorization of }B(x)\\
D(x)&=\sum_{i=1}^{x}C(x)
\end{align}
$$
Input:

First line: $T$ [number of test cases]
Each test case consists of an integer $N$

Output format
For each test case, print a single integer denoting the value of $D(N)$ in a new line.
Input constraints
$$\begin{align}1\leq T\leq 10^6\\1\leq N\leq 10^6\end{align}$$

Here's my observation:

About the constraints, there are 10^6 test cases, each test case can be as large as 10^6, I estimate we need an algorithm that is at least O(nlogn). Otherwise we will have TLE.

I guess this problem is a math one. We somehow need to come up with an efficient formula to resolve all 4 functions.

I know for sure if we solve this problem naively, we cannot pass all test cases. Even if we use the best method to compute gcd and prime factor.

I've thought about this one for two days I can't find an acceptable solution for this problem. You can assume that this problem have time limit of 5 seconds.

Since this is a math problem, some talented and gifted genius out there might be interested. :D
Please help to come up with a formula to solve this, or provide an understandable solution. Thank you very much.

Let me put together the two comments.
The function $A$ is Euler's totient function, which is often called $\phi$.
The function $B(x)=\sum_{d|n}\phi(d)$ is known to be equal to $B(x)=x$.
Now, observe that $D(x)=\sum_{i=1}^{x}C(B(i))=\sum_{i=1}^{x}C(i)=C(x!)$, where the last equation is because $C$ satisfies $C(a)+C(b)=C(ab)$.
Now, if $p_1<p_2<\ldots<p_k$ are the primes less than or equal to $x$ and $x!=p_1^{a_1}p_2^{a_2}\dotsm p_k^{a_k}$, then $$C(x!)=a_1+a_2+...+a_k$$
We can use Legendre's formula to compute each $a_i$. Note that the formula doesn't need to compute $x!$, but it computes $$a_i=\left\lfloor\frac{x}{p_i}\right\rfloor+\left\lfloor\frac{x}{p_i^2}\right\rfloor+\left\lfloor\frac{x}{p_i^3}\right\rfloor+\ldots$$
where there are actually finitely many summands.
So, an algorithm to compute $D(x)$ can be:

Compute the primes $p_1,p_2,\ldots,p_k$ up to $x$. This can be done using some sieve, like Erathostenes' or Atkin's
Then for each prime evaluate Legendre's formula above, which takes about $\log_{p_i}(x)$ divisions.


Minimal paths as solution of a linear program of a special network flow Let $G= (V,E)$ be a given directed weighted graph, and $s,t$ two specified nodes, so that there is no negative cycle reachable from $s$, and $t$ is reachable from $s$.
We're looking for the shortest s-t-path.

By regarding this problem as a special flow network, we can express this using linear programming as follows :

Minimize the function:
$$ \sum_{e\in E} c_e\cdot x_e $$

Under the constraints:
$$
\forall v\in V-\{s,t\}: \sum_{e\in in(v)}x_e -\sum_{e\in out(v)} x_e = 0
\\
\sum_{e\in out(s)} x_e = 1
\\
\sum_{e\in in(t)} x_e = 1
\\
\sum_{e\in in(s)} x_e = 0
\\
\sum_{e\in out(t)} x_e = 0
\\
\forall e\in E: x_e \ge 0
$$

Here $c_e$ are the weights of the edges, $in(v)$ are all edges going into $v$, and $out(v)$ are all edges starting in $v$.

About the correctness:

Let $S$ be a solution to above linear program. As the constraints are the same as for network flows (if we see each edge as having infinite capacity), $S$ is a flow on $G$.

Given that every $s-t$-path fulfills the constraints, we can conclude that if $S$  is an  $s-t$-path, then it is an $s-t$-path with minimal costs.

Further, $S$ can't contain any cycle with positive weight, as we could simply remove this cycle from $S$ and end up with a lower-cost solution that fulfills the constraints.

Finally, $S$ has to be an $s-t$-path. Let's assume $S$ wasn't. Given that $S$ is a flow, we know that it has to contain some $s-t$-path. So let $M$ be the set of all $s-t$-paths that $S$ contains.
 Then there is a path with minimal costs in $M$ (as $S$ is cycle-free, and therefore there can only be finitely many elements in $M$). Let this $s-t$-path be $p_{min}$.

If we let $c: M\to \mathbb R $ now be the map that assigns each $s-t$-path in $M$ its cost, we obtian the following inequality:
$$1\cdot p_{min} \le \sum_{p\in M} \lambda_p \cdot p \qquad\text{ given that } \forall p\in M: \lambda_p \ge 0 , \sum_{p\in M} \lambda_p = 1$$

Therefore, if $S$ would contain multiple $s-t$-paths, it wouldn't be minimal.

Thus we can conclude, that $S$ is a minimal $s-t$-path.

My question now is: Did I miss something in the proof?

Addendum:

It turns out that the above proof needs that each $s-t$-path has a unique cost. Otherwise, there might be no single $s-t$-path with minimal costs. In this case,  it can't be shown that the solution $S$ only contains a single of those paths with minimal costs.
However, in this case, by the reasoning above, it still is true that every path in $S$ is optimal. So in this case, we can just pick any path in $S$ as solution (which we can find using e.g. DFS)

Some final (off-topic) remarks:
This whole procedure seems like a lot for a less efficient method to obtain a shortest path. What caught my eye were the following two properties of this algorithm:
$(i)$ Besides the non-negativity constraint, all constraints are actually equalities.
$(ii)$ The algorithm should be easily adaptable to also allow for negative cycles (by putting some linear restriction on the solution, e.g. that the path mustn't be too long, etc.)

There is a major flaw in your question: You presented a shortest path formulation and not a special case of a network flow problem.
Your objective function minimizes the cost of the path. The next 5 constraints are the classic flow constraints, which ensure a path between $s$ and $t$. The last constraint is just the bound of variable $x$.

Now, we can start answering your questions:

  Given that every s−t-path fulfills the constraints, we can conclude that if S is an s−t-path, then it is an s−t-path with minimal costs.

Correct. It is the shortest path on the defined graph.

  Further, S can't contain any cycle with positive weight, as we could simply remove this cycle from S and end up with a lower-cost solution that fulfills the constraints.

The solution of a shortest path problem does not contain a cycle, for obvious reasons.

  Did I miss something in the proof?

Sorry, but your proof does not show anything. You are showing that the shortest path is the shortest path.

  This whole procedure seems like a lot for a less efficient method to obtain a shortest path

Because you are solving the shortest path problem :)
However, I still recommend you to stick with Dijkstra's algorithm, which is faster than linear programming.

  Besides the non-negativity constraint, all constraints are actually equalities.

Yes, good observation. You just have the classic flow constraints (which are all equalities). I recommend you to read the Ahuja's book on network flows (is the best I know, by the way).

  The algorithm should be easily adaptable to also allow for negative cycles (by putting some linear restriction on the solution, e.g. that the path mustn't be too long, etc.)

You can do that. However, this constraint lies in enumerating all the cycles of your graph, which cannot be fastly solved.


is size of maximum matching less than that of maximum k-parity k-set packing? My application problem can be modeled as maximum k-parity k-set packing problem, which is NP-hard. I know that maximum matching is polynomial time, hence I want to reduce k-parity k-set packing into bipartite maximum matching. I am wondering if there is any relation between their size.

Maximum k-parity k-set packing problem: We're given a universe $U$, which is a union of $k$ disjoint sets, $ U = V_1 \cup \cdots \cup V_k$, and a family $ \mathcal{S} $ of subsets of $ U$, each $S$ contains exactly one vertex
from each set, i.e., $S \in V_1 \times \cdots \times V_k$. A packing is a subfamily ${\mathcal {C}} \subseteq {\mathcal {S}}  $ of sets such that all sets in  ${\mathcal{C}}$ are pairwise disjoint.  The size of that packing is  $|{\mathcal  {C}}|$. We are looking for the maximum-size packing.

In order to take advantage of polynomial time maximum matching we reduce $U$ to $U' = V_i \times V_j, i , j = 1, \cdots, k$ and $\mathcal{S}'$ be a family of subsets of $U$ such that each $S'$ contains exactly one vertex from $V_i$ and $V_j$. Let $d_{i,j}$ be the size of maximum matching and $d = \min_{i,j} \{d_{i,j} \}$.

For example in the figure below: $|C| = 2, d_{2,3} = d_{1,2} = d_{1,3} = 2$ hence $d = \min(2,2,2) = 2$.

My question: is this inequality true
$|{\mathcal  {C}}| \le d \le k \times |{\mathcal  {C}}|$ ?

I think $|{\mathcal  {C}}| \le d$ is obvious, do we also have $ d \le k \times |{\mathcal  {C}}|$?

Consider the case $k=3$, and the following set system:
$$
(a_1,b_1,c),\ldots,(a_n,b_n,c) \\
(a'_1,b',c'_1),\ldots,(a'_n,b',c'_n) \\
(a'',b''_1,c''_1),\ldots,(a'',b''_n,c''_n)
$$
Every packing contains at most 3 sets, but $d=n+2$.


Proving a language is not regular using Myhill Nerode Theorem Let $L = \{\alpha\in\{a,b,c\}^{*} \mid \alpha \text{ is palindrome}\}$, show that $L$ is not regular using Myhill-Nerode relation.

I don't know how to show that $L$ has infinite equivalence classes because $\alpha$ is a palindrome. I tried to use something like this, but I don't know if its correct:

$\alpha \equiv_{L} \beta \iff \alpha (aba)^k \in{L} \iff \beta (aba)^k \in{L}$ $\forall k \in \mathbb N$ which implies that for every k there exists an equivalence class because the repetition of aba k times.

Take $a^nb$ and $a^mb$ for n != m. Since the first can be followed by $a^n$ and the second can’t, they are in different equivalence classes. Therefore the number of equivalence classes is not finite.

C isn’t even needed.


Need help understanding a derivation of "witnesses" for a Landau bound So here's an excerpt from Foundations of Computer Science by Alfred Aho and Jeffrey Ullman[1]. I've also found basically the same material in a few other places, and also in my discrete math textbook, but this is clearest one I've seen:

  Example 3.2. Suppose we have a program whose running time is $T(0) = 1$, $T(1) = 4$, $T(2) = 9$, and in general $T(n) = (n + 1)^2$. We can say that $T(n)$ is $O(n^2)$, or that $T(n)$ is quadratic, because we can choose witnesses $n_{0} = 1$ and $c = 4$. We then need to prove that $(n + 1)^2 \leq 4n^2$, provided $n \leq 1$. In proof, expand $(n + 1)^2$ as $n^2 + 2n + 1$. As long as $n \leq 1$, we know that $n \leq n^2$ and $1 \leq n^2$. Thus $n^2 + 2n + 1 \leq n^2 + 2n^2 + n^2 = 4n^2$.

Even so, I get lost where it says:

$$
n^2 + 2n + 1 \leq n^2 + 2n^2 + n^2
$$

I get that it's true, but it seems arbitrary. How/why did the expression get modified on the right side of the $\leq$ like it did? Couldn't they also have done this?

$$
n^2 + 2n + 1 \leq 4n^2 + 0 + 0
$$

Specifically, what rule did they apply to transform the expression $n^2 + 2n + 1$ into $n^2 + 2n^2 + n^2$?

http://infolab.stanford.edu/~ullman/focs.html

They want to end up with  constant * n2  on the very-right.

They applied "make each term a constant times n2".


Could two decidable languages ever not have a mapping reduction? Is it ever the case that two decidable languages $L_1$ and $L_2$ that cannot be reduced to one another (in either or both directions)? Intuitively, I would not expect there to be, but rigorously, are there extreme examples that prove otherwise?

If you are talking about reduction in general (not polynomial reduction), then you basically can put all the logic in the reduction function. Suppose $L_1$ and $L_2$ are decidable languages. To reduce $L_1$ to $L_2$ we need a computable function $f$ such that $x\in L_1 \Leftrightarrow f(x)\in L_2$. The function $f$ just works as follows. Given a word $a\in L_2$ and a word $b \notin L_2$:

  $f(x) = \begin{cases} a & \text{if } x \in L_1 \\ b & \text{if } x \notin L_1 \end{cases}$

This function is computable because $L_1$ is decidable by assumption.

However, the above also points you to the exceptions. It assumes that there is a word $a\in L_2$ and a word $b\notin L_2$, and there exactly two languages for which this is not the case. Both of those languages are decidable.


What's the average number of clauses modern SAT solvers can handle? It's already known that size doesn't matter always (for SAT problems).

But is there evidence (from real data from: benchmarks or real cases) on how many clauses an average SAT solver can handle nowadays?

Another issue that derives is that once they find a solution, most don't stress the fact about finding alternative solution. Is there a reason?

You're asking two questions.  I'll answer your first question.

There's no simple answer.  It depends on the structure of the problem.  There are problems with millions of clauses that can be handled by a SAT solver.  There are also problems with only tens of thousands of clauses (perhaps fewer) that can't be handled by SAT solvers.

The number of clauses isn't a great predictor of whether a SAT solver will be able to solve the problem in a reasonable amount of time.

Rick Decker has answered your other question.


P=NP giving a deterministic algorithm for SAT I'm trying to prove the following problem:

Prove that if $P=NP$ then there is a polynomial time algorithm for the following problem:
INPUT: A boolean formula $\phi$.
OUTPUT: A satisfying assignment of $\phi$ if $\phi$ is satisfiable. If $\phi$ is unsatisfiable, return $false$.

My proof:
If $P=NP$ then $SAT$ can be decided in polynomial time. Run $SAT$ on $\phi$. If it returns $false$, reject. Else, nondeterministically select a boolean assignment. If it satisfies $\phi$, return it.
The algorithm is in $NP$, but because $P=NP$, it is also in $P$.
Is my proof correct? I'm asking because the textbook gave a different answer, and I want to know if my proof is correct, and if not, where does it fall?

I like the way you think, but there's a gap in your attempt.

$\mathrm{P}$ and $\mathrm{NP}$ are classes of decision problems, i.e., computational tasks where the answer is either "yes" or "no". Nondeterministically generating a satisfying assignment isn't a decision problem, so it isn't in $\mathrm{NP}$, so the assumption that $\mathrm{P}=\mathrm{NP}$ doesn't give you a deterministic algorithm for it. It feels like it ought to, but that's not a proof.


Find the minimum count of elements summing to a pre-defined sum We have the following problem: Given an array of integers $\{a_1, a_2,...,a_n\}$ and a number $s$, find a contiguous sub-array of elements that sum exactly to $s$. If multiple solutions exist, find a solution that is smallest in terms of length (length of sub-array). If there is no such contiguous sub-array, output "-1".

I have thought of an $O(n^2)$ algorithm, using two pointers and prefix sums, but I cannot find an $O(n)$ algorithm. What would an $O(n)$ algorithm be like?

This can be solved in $O(n \lg n)$ time by computing prefix sums and then using divide-and-conquer.

Step 1. Compute the prefix sums $p_0,p_1,\dots,p_n$, where we define $p_i = a_1 + a_2 + \dots + a_i$.  Throw away the $a_i$'s.  Now the problem becomes: count how many index-pairs $i,j$ there are where $0 \le i \le j \le n$ and $p_j = p_i + s$.

Step 2. Solve this problem using divide-and-conquer.  First, count the number of solutions where $0 \le i \le j \le n/2$ (recursively).  Second, count the number of solutions where $n/2 < i \le j \le n$ (recursively).  Third, count the number of solutions where $0 \le i \le n/2$ and $n/2 < j \le n$.  This third step can be done in $O(n)$ time (expected running time).  Since this is your exercise, I'll let you work out how: it's not too hard.

The total running time satisfies the recurrence $T(n) = 2 T(n/2) + O(n)$, so this yields a $O(n \lg n)$ time solution.


What is von Neumann bottleneck? According to this Quora post,

  It refers to two things: A systems bottleneck, in that the bandwidth
  between Central Processing Units and Random-Access Memory is much
  lower than the speed at which a typical CPU can process data
  internally. The 'intellectual bottleneck' in that programmers at the
  time spent a lot of time thinking about code optimisation to stop
  'lots of words' being pushed back and forth between CPU and RAM.

But according to my class lecture, it is the problem that "Generic implementation of single, common instruction and data hierarchy makes it impossible to access data and instructions at the same time. This is traditionally called von Neumann bottleneck."

Which one is correct?

Both are correct, though I'd say the first one more so.

A von Neumann architecture means the program is stored in memory along with everything else, rather than being a separate unit attached to the processor. This means that anything the computer tries to do, no matter what it might be, is bottlenecked by the connection between the processor and memory.

So "getting data from memory is slower than processing it" is a valid description, as is "you need to fetch instructions and you need to fetch data and both of those are slow". But the most important part is that fetching from memory is extremely slow compared to anything else the processor might be doing.


Advantages of adaboost over gentleboost in applications, or vice versa? I've been researching on AdaBoost and GentleBoost classifiers, but can't seem to find a clear answer to the question:

What is Adaboost better at classifying in computer vision?
What is GentleBoost better at classifying?

I've been told that AdaBoost is good for things with soft edges, like facial recognition, while GentleBoost is good for things with harder and more symmetrical features and edges, like vehicles. Is this true? Is there any proof for this or any evidence to back up this claim?

Genetellboost is developed to cope with labeling noise, i.e., when some samples are wrongly labeled. Though, it wasn't so successful in that respect, from my experience it is quite good in handling noisy features which are kind of outliers in dataset. That being said, there is no proof for neither of the things that you asked (nor the things that you mentioned are true). In fact, we know that these algorithms are so similar that it is practically impossible to predict which one works better on which dataset. You have to test it and that's it.


Relation between "syntax" and "grammar" in CS I do sure that "grammar" and "syntax" is two different thing in CS, e.g

  Syntax of Java language is defined by a context-free grammar.

My question are

What is different in definitions of "grammar" and "syntax" in CS?

What is relation between them, can we describe it by using set theory?

Your quote has the following operational meaning for syntax in the context of programming languages:

  The syntax of a programming language is the set of all syntactically valid programs.

The syntax only describes what the valid programs look like; semantics gives them meaning – tells you how to execute them.

The set of all valid programs is an example of a formal language; a formal language is just a collection of strings. There are many ways of describing formal languages. One of them is through formal grammars, which you can think of as a type of formula that describes a formal language. Context-free grammars are a restricted type of formal grammars. As such, they cannot describe all formal languages, but only context-free languages. (General grammars also describe only some of the formal languages; this is due to the fact that there are countably many grammars but uncountably many formal languages.) Summarizing:

  A grammar is one way to specify a formal language.

Finally, let me mention that the set of syntactically valid Java programs actually cannot be described by a context-free grammar; only some features can be described. Context-free grammars cannot enforce, for example, that a variable not be defined twice in the same context. However, once we abstract away such details (for example, by replacing variable names with generic placeholders), the resulting set of syntactically valid Java programs does lend itself (perhaps) to being captured by a context-free grammar.

Parsing (in our context) is the process of reading the source code of a Java program and constructing its parse tree, which is its structure as seen from the perspective of the context-free grammar. The parse tree captures the semantics of the program in a form amenable to further manipulation in the compilation process. Abstracting away details such as variable names and values of constants relegates this information into the form of parameters, but doesn't obstruct the control structure of the program.


if A is in P and B is NP, is A ≤p B? if A is in P and B is NP, then is A polynomial time reducible to B?

Could anyone prove a prove or disprove for it?

If $B$ is neither empty nor the universal set, then the reduction can be performed and is trivial.

You need to have two strings $w_1 \in B$ and $w_2 \notin B$. In the reduction of membership problem $(A,x)$, we trivially solve the membership in $A$ in polynomial time: if $x \in A$ then return $w_1$ else $w_2$.


Understanding LEADING and TRAILING operations of an operator precedence grammar I want to understand what the LEADING and TRAILING of non-terminal in an operator precedence grammar physically mean.

I am confused by the various definitions I have read on them.
I understand that the LEADING of a non-terminal is the first terminal which can be present in it's derivation.
On the other hand, the TRAILING of a non-terminal is the last terminal which can be present in it's derivation.
In the following example:

E   ->  E   +   T      -- I
E   ->  T              -- II
T   ->  T   *   F      -- III
T   ->  F              -- IV
F   ->  (   E   )      -- V
F   ->  id             -- VI

By my understanding,

LEADING(E) = { +, *, (, id }
LEADING(T) = { *, (, id }
LEADING(F) = { (, id }

This turns out fine, but my problem is in the TRAILING.

TRAILING(F) = { id, ) }
TRAILING(T) = TRAILING(F) = { id, ) }          -- (1)
TRAILING(E) = TRAILING(T) = { id, ) }          -- (2)

Reason for (2) is that according to productions I and II, the last terminal of the derivation of E will be last terminals in the derivation of T.
Hence, TRAILING(E) = TRAILING(T).
Similarly, TRAILING(T) = TRAILING(F).
Unfortunately the solution to this problem states:

TRAILING(F) = { id, ) }
TRAILING(T) = TRAILING(F) `union` { * } = { *, id, ) }
TRAILING(E) = TRAILING(T) `union` { + } = { +, *, id, ) }

I don't see how * or + can be the last terminals in the derivation of E. Any derivation of E will always end with either an id or ). Similarly, case for T.

@Raphael : Definition of trailing : Any terminal which is present at the last of a right sentential form (and not the sentence) which is derived from a non-terminal is the trailing of that non-terminal.

Trailing($E$) :

$E \rightarrow E + T$  --In this the trailing is '$+$'

$ \rightarrow E + T * F$ [using $T \rightarrow T*F$] -- Here trailing is '$*$'

$\rightarrow E + T * ( E )$ [using $F \rightarrow ( E )$] -- Here trailing is '$)$'

(from $E + T * F$) $\rightarrow E + T * id$ [using $F \rightarrow id$] -- Here trailing is '$id$'

Hence trailing($E$) = $\{+,*,),id\}$

So the lesson here is that you must use the right sentential forms also and not just the sentence to find out the trailing.

Note : $E \rightarrow E + T \rightarrow E + T * F \rightarrow E + F * id \rightarrow T + id * id \rightarrow F + id * id$ are all right sentential forms of $E$ as they have at least one non-terminal.

However $id + id * id$ is a sentence because it has no non-terminals and you must not use just the sentence to find out the trailing.


Is equivalence of a CFG and an RG undecidable? I know that the equivalence of two context-free grammars is undecidable, but what about the equivalence of a regular grammar and a context-free grammar?

It is undecidable whether for a given CFG $G$, $L(G)=\Delta^*$, the set of all strings (over the terminal alphabet of $G$). That answers your question, by chosing the most simple regular grammar.


Minimum variable size if the information are coded in non-binary system A typical HDD would represent information as either 1 (e.g. spin up) or 0 (e.g. spin down). Let's assume you want to represent the information physically in a hex system with 16 states, and assume this is possible with using some physical form (maybe the same spin).

What is the minimum physical size of a memory element in this new system in units of binary bits? It seems to me that the minimum is 8 bits = 1 byte. Therefore, going from a binary representation to a higher representation will, everything else equal, make the minimum variable size equal 1 byte instead of 1 bit. Is this logic correct?

One hexadecimal digit contains 4 binary digits. You can compute this as follows: $\log_2 16 = 4$. Alternatively, $2^4 = 16$. So the minimal memory element will contain 4 bits' worth of information.

This also works when the number of states is not a power of 2, but you have to be more flexible in your interpretation.


Decision problems: Does a "constant" characteristic function describe a language in P? I am new to complexity theory and I have some maybe stupid questions:

Are "decision problems" with the characteristic functions x(t)=1 or x(t)=0 "decision problems" or not?

If yes: Are the corresponding formal languages members of P or not?

(The calculation time needed is constant.)

If the answer is yes in both cases:

If $P\neq NP$ no P decision problem can be NP-complete. This is easy to prove.

I have read that if $P=NP$ all P decision problems would be NP-complete. This is easy to prove for all other problems however the problems described above cannot be complete in any way.

Are these problems an exception?

Yes, of course they're in P: you can decide them in constant time, which is certainly bounded by a polynomial.

Anybody who tells you that P$\,=\,$NP implies that every problem in P is NP-complete has forgotten about these two trivial problems. Neither of them can be NP-complete, because NP-completeness is defined in terms of many-one reductions, but there cannot be a many-one reduction from a non-trivial probelm to either of the trivial problems. A many-one reduction from $A$ to $B$ must map "yes" instances of $A$ to "yes" instances of $B$, and "no" instances to "no" instances.  But one of the trivial problems has no "yes" instances and the other has no "no" instances, so a problem that has both "yes" instances and "no" instances cannot be reduced to either.


Designing DFA for accepting a string with a 1 in the tenth place from the right over an alphabet {0,1} I'm stuck trying to implement a DFA to do this. Everything I've tried so far seems to have to be able check the next nine elements to determine if the string terminates. Any tips?

Your idea is correct.

Using the Myhill-Nerode theorem, it can be proven that the DFA for this language with the minimum number of states has $2^{10}=1024$ states.

Firstly, it is easy to see that the language is regular using an NFA of $11$ states. In the start state, have transitions for $0,1$ to itself, and a transition for $1$ to another state. From there, have a single common transition for $0,1$ from a given state to a new state each time. The last state is the final state. Thus, the string is accepted if $10$ characters earlier, the symbol was a $1$, which enabled the strings symbols to enter this "chain".

Your equivalent DFA will need to remember the each of the last $10$ symbols, which give $2^{10}$ combinations. It can be shown that every string using the given alphabet can be divided into $2^{10}$ equivalence classes over this language, one for each combination.

For any two strings over this alphabet, if they have the last $10$ symbols the same, then every string appended will result in either both being accepted by the language or both rejected by the language. They will be accepted if the first symbol is a $1$, and rejected otherwise. So, they are equivalent.

For any two strings whose last $10$ symbols are not the same, there must exist some position where they differ. By simply appending any string such that the resultant string has the symbols from this position at $10$ places from the end, one must be accepted and the other must be rejected. So, they cannot be equivalent.

If the number of symbols are less than $10$, prepend with leading zeroes, and the argument still holds.

Thus, we have $2^{10}$ equivalence classes, and by the Myhill-Nerode theorem, any DFA for this language must have at least $2^{10}$ states.