Decomposing NP-hard sets Suppose A∪B is NP-hard, does it follow that A is NP-hard or B is NP-hard?

Equivalently, is the property "not NP-hard" closed under union?

A related question was already asked:

Are NP-complete sets formed from two other sets only if at least one is NP-hard?

but it seems no consensus was formed.

If $P = NP$, then the only not-$NP$-hard sets are $\emptyset$ and $\Sigma^*$, and the statement trivially holds. So let us assume $P \neq NP$.

Then whenever $X$ is $NP$-hard, both $X$ and $X^C$ must contain an infinite c.e. set, namely "the image of the positive SAT-instances under the reduction" and "the image of the negative SAT-instances under the reduction". For if either of these sets were finite, we could get a P-algorithm for SAT.

By diagonalization, we can construct some set $X$ such that neither $X$ nor $X^C$ contain an infinite c.e.-set. Then $SAT \cap X$ and $SAT \cap X^C$ do not contain infinite c.e. sets, hence are both not $NP$-hard. But their union is SAT, and hence $NP$-hard.

To get a decidable counterexample, it should suffice to note that if $X$ is NP-hard, we not only have infinite c.e.~subsets of $X$ and $X^C$, but actually ones which can be computed in exponential time. Diagonalizing against those should doable in a decidable way; but I have not worked out the details.


Word-hyphenation algorithm for monospaced fonts I have seen a few standard hyphenation algorithms for non-monospaced fonts, where you are free to squeeze and separate words and letters, but I haven't seen any related to monospaced fonts specifically. Wondering if there are any good resources on the topic. Such as how to best properties to use when hyphenating a monospaced word, etc.

I assume you are asking about algorithms to decide where to split lines when formatting paragraphs, not about algorithms for deciding where it is legal to insert hyphens into a word?

All algorithms for this kind of problem go back to Knuth, Donald E.; Plass, Michael F. (1981), "Breaking paragraphs into lines", Software: Practice and Experience 11 (11): 1119–1184, doi:10.1002/spe.4380111102, which is also described in this entry on tex.stackexchange: https://tex.stackexchange.com/a/109818/28084.

The key is to define an objective function and then come up with an efficient algorithm for optimizing the objective function.  Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, 3/e, 2009 gives a super-simplified version in problem 15-4 (page 405) that asks you to minimize the objective function "sum of cubes of number of extra spaces required on each line" using an efficient dynamic programming formulation.

In Knuth and Plass they demonstrate that a bunch of variants of the objective function (including adding a linear penalty for each hyphenation break that is added, and accounting for the extra space consumed by the hyphen) don't require you to go beyond the efficient dynamic programming formulation.


Is Bin-Packing with only 2 types of objects polynomial? Is the following problem polynomial ? Or NP-Complete ?

Problem: Bin packing with 2 types of objects.

Input: $C$, the capacity of each bin, $N_a, N_b$ the numbers of objects $a$ and $b$, $w_a,w_b$ the weight of the objects, $k$, the maximum number of bins.

Output: Yes if all objects fit in the $k$ bins without exceeding the capacity of any bin or cutting objects, No otherwise

My first intuition was that with only two types of objects, there must be less solution and maybe enumeration is polynomial, so I tried count them.

For an instance of size $n$ (with $n$ objects), we can encode solutions as $n$-tuples $[0,1,1...,0,1]$ (the first objects being in the first bin until it's full, then the second, etc). For instances of size $n$, there are $2^n$ distinct solutions.
Since there are $n$ instances of size $n$ (I mean, $n$ pairs $(N_a,N_b)$ such that $N_a+N_b=n$), and by the pigeonhole principle, there must be an instance with at least $2^n/n$ solutions. So a simple enumeration of solutions doesn't work.

Then, I started thinking that the problem may be NP-Complete. Reducing a graph problem seems no to be a good idea: graphs are big structures, and this problem as only a few numbers as an input. At this point, I realized that all the NP-Complete problems I've heard of had biggers inputs.

Now, I'm a bit confused. I can't figure out a good algorithm or a reduction.

The problem can be solved in polynomial time. See A Polynomial Algorithm for Multiprocessor Scheduling with Two Job Lengths, An Asymptotically Exact Algorithm for the High Multiplicity Bin Packing Problem, or On the bin packing problem with a fixed number of object weights.


Binary digit problem? Question:

  If a system has $32k$ bytes and each such byte has unique address(so $32k$ addresses), what is the smallest possible bits that can be use by every byte for the address ? All the bytes use the same number of bits for the address.

I thought the answer can be found by finding the value to which $2$ can be raised such that it equals $32,000$. I got $2$ raised to $ \sim 14.96$ gives $32,000$. But a byte only has $8$ bits so this can't make any sense.

Can anyone give any pointer on how to solve this problem ?

The system has 32.000 bytes and each byte must have its own unique address:

32.000 unique addresses

How many bits to represent these?

$2^{15} = 32768$, so if we let addresses be 15 bit we have the address space $[0,32767]$.


Why is this implementation of the hash function bad? I have a task of hashing DNA sequences. Let the DNA be long sequences of four amino acids, which we will denote by the letters $A, T, G$ and $C$.
My hash function $h$ take DNA as an input and return the sum of amino acid numbers by some large simple modulus as a hash, and then add it to a hash table with a public key. Why is this hashing implementation bad?

Because

two sequences with the same acids in different order (e.g. two acids switch places) will have the same hash code;

this will only produce numbers from 0 to your large simple modulus instead of all $2^{32}$ or $2^{64}$ possibilities.


NP-completeness of a spanning tree problem I was reviewing some NP-complete problems on this site, and I meet one interesting problem from

NP completeness proof of a spanning tree problem

In this problem, I am interested in the original problem, which the leaf set is precisely $S$. The author said that he can prove this by reducing it to the Hamiltonian path. However, I still cannot figure it out. Could anybody help me with this in details?

Seems this question has been bumped by the system because it has no answer yet:

The idea JeffE proposed is to reduce the Hamiltonian Path problem (a known NP-complete problem) to this version of the spanning tree problem.

This is not hard to do: given a graph and two nodes we want to find an HPath between, we can set S to the set containing those two nodes and ask for a spanning tree with those nodes as leafs. Since a tree with just two leaves is a path, and a spanning path (that goes through all the nodes) is a Hamilton path, we can see how its possible to use an algorithm for the spanning tree eproblem to solve any Hamilton Path problem.

This proves that the spanning problem is NP-Hard. Since the problem is also clearly in NP, we thus can conclude that its NP complete.


Is the mate-in-n problem of infinite chess with each color using traditional pieces plus one huygens decidable? I noticed in a paper that the mate-in-n problem of chess, even played on an infinite board is decidable. The mate-in-n problem of inﬁnite chess is decidable

I believe the paper assumes only traditional chess pieces are used.

What if one of the chess pieces is a huygens? (A huygens is a chess piece which jumps prime numbers of squares).

Is the mate-in-n problem of chess on an unbounded board with each color using traditional chess pieces plus at least one huygens also decidable?

Presburger arithmetic with a predicate for the primes is probably undecidable, so at least the technique used by your question's link should not easily generalize to allowing a huygens.

For example, although decidability of the special case I'm about to mention

would follow from there being only finitely many positive even integers that

are neither prime gaps nor sums of two distinct primes, I don't see any way of

proving decidability of mate-in-ONE for king+huygens against a smothered king:


this language and acceptance by queue automaton I don't know how to prove or show that:
$ L_1 = \{xx|x \in \Sigma^\ast\} $ (that can be accepted by queue automaton)
If it would be possible, show by deterministic queue automaton, if not, by non-deterministic queue automaton.
If it's not that hard (and if I can), please give me a hint.
Thanks in advance.

Working with a queue automaton for me is intuitively equivalent to working with a circular tape.
Read the input $w$ from the automaton, and put it on the tape. Add two markers $A$ and $B$, so we obtain $Aw_1Bw_2$. Now we can one by one eat a letter after $A$ and one after $B$.
For the deterministic variant it suffices to put $B$ exactly in the middle of the input string. That position can be found using a method similar to this: How to find middle element of linked list in one pass?


What is the 1's and 2's complement of 0.01101? What is the 1's and 2's complement of 0.01101?
I'm unable to find any details on this from google.

Basically how do we represent the floating points in 1's and 2's complement forms?

Even wikipedia only says that 1's complement is the inverted bits of binary representation. The examples only contain integer values. I couldn't find anything clear about what is the exact significance of this system. Hence, unable to deduce if the inverting bits applies to floating points also.

One's and two's complement apply to (fixed-point) encodings of integers.  They don't apply to floating-point numbers.  Floating point is different.


Linear programming formulation of cheapest k-edge path between two nodes Given a directed graph $G = (V,E)$ with positive edge weights, find the minimum cost path between $s$ and $t$ that traverses exactly $k$ edges.

Here is my attempt using a flow network:
\begin{align}
\min \sum_{(i,j) \in E} c_{ij}x_{ij}
\end{align}
\begin{align}
\sum_{j \in V} x_{ji} - \sum_{j \in V} x_{ij} &=
\begin{cases}
    -1,& \text{if } i = s\\
    1,              & \text{if } i = t\\
0, & \text{otherwise}\\
\end{cases} && \forall i \in V\\
\sum_{(i,j) \in E} x_{ij} &= k &&\\
x_{ij} &\geq 0 && \forall (i,j) \in E\\
\end{align}

However, this doesn't eliminate cycles which are disjoint from the $s$-$t$ path. I can use subtour elimination constraints like in the Miller Tucker Zemlin formulation of the Travelling Salesman Problem but this enforces a simple path making the problem harder than it should be.

Any ideas on alternative formulations?

Update: This is part of a slightly bigger formulation here, where $z$ is a slack variable which scalarizes multiple objectives with a rectified-linear function:

\begin{align}
\min \sum_{k \in K} z_{k}
\end{align}
\begin{align}
\sum_{(i,j) \in E} c^{k}_{ij}x_{ij} - z_{k} &\leq 1 && \forall k \in K\\
\sum_{j \in V} x_{ji} - \sum_{j \in V} x_{ij} &=
\begin{cases}
    -1,& \text{if } i = s\\
    1,              & \text{if } i = t\\
0, & \text{otherwise}\\
\end{cases} && \forall i \in V\\
x_{ij} &\geq 0 && \forall (i,j) \in E\\
\end{align}

Solutions are integral when solving with a linear program, but suggestions for more efficient algorithms would be appreciated.

The simplest way to compute the shortest path from $s$ to $t$ that traverses exactly $k$ edges is by increasing the size of the graph $k$-fold.

In particular, make $k$ copies of the vertices and $k-1$ copies of the edges, where for each edge $(u,v)$ in the original graph, we add an edge from the $i$th copy of $u$ to the $i+1$th copy of $v$ (for all $i$).  Now look for the shortest path from the 1st copy of $s$ to the $k$th copy of $t$ using a standard algorithm (e.g., Dijkstra's algorithm).  The running time will be $O(kn+km\lg(kn))$.

Only you can determine whether this kind of formulation will be compatible with your additional constraints and objective function (since you haven't told us what they are), but this kind of modification to the graph is a general approach for this sort of problem that is pretty flexible and might meet your needs.

You could presumably also combine this with your network flow / LP formulation.  Now there will be no cycles that can show up, as the resulting graph is acyclic (a dag).  I don't know if that will meet your needs.


proving {$a^ib^jc^k : j = i \lor j = k$} is not regular i had troubles proving this  is not regular using the pumping lemma {$a^ib^jc^k : j = i \lor j = k$}. Not sure how to approach this anymore, and help would be appreciated

If you intersect your language with $a^+ b^+$ then you get $\{ a^n b^n : n \ge 1 \}$, whose irregularity you probably know how to prove.


Understanding an example of coin toss expectation maximization I've been trying to get my head around Expectation maximization algorithms, and I thought I'd start simple. I found this 3-coin example here: http://cs.dartmouth.edu/~cs104/CS104_11.04.22.pdf  I understand the calculation of all of the probabilities but I don't understand how the recalculation of lambda, p1 and p2 is actually done. (Page 18)

I understand how the maximization of a log-likelihood/likelihood function by differentiation works, but can't figure out the recalculation method here.

Can anyone explain why the recalculation of lambda, p1 and p2 take the form they do?

From mcdowella's answer to IcySnow's question Expectation Maximization coin toss examples, Michael Collins' EM Algorithm (pdf) paper presets the "Three Coins Example" in section 3.1 (pdf page 8-9) and explains the steps for recalculating the parameters $\lambda, p_1, p_2$ in accordance with the EM Algorithm.

The derivation is too lengthy to type up here, but to summarize, you'll formulate the conditional expectation in terms of the previous iteration of parameter values and then differentiate the expectation with respect to each parameter from the previous iteration then perform algebra to obtain the maximum after setting the derivative to zero.


Solving $T(n) = 4T(n/2) + n^3$ with substituton method I am trying to solve the following recurrence $T(n) = 4T(n/2) + n^3$ with substitution method. My guess is $T(n) = \Theta (n^3)$ (I used master theorem) and I tried to show that $T(n) \leq cn^3$. But, when I substitute I got $T(n) \leq c \frac{n^3}{2} + n^3$ and that's it not the exact form of the guess, so it doesn't work. How can I solve this recurrence?

Your guess works: if $T(n) \le c n^3$ and $c \ge 2$ then
$$
T(n) = 4c \frac{n^3}{8} + n^3 = \frac{c}{2} n^3 + n^3 = cn^3 \left(\frac{1}{2}+\frac{1}{c} \right) \le cn^3.
$$


Enumerating sets in a random order I have multiples arrays. I'd like to enumerate all sets containing exactly one item from each array in a (pseudo-)random order, without explicitly building the array of all sets.

Any solution, even with poor pseudo-randomization, is welcome.

EDIT: Example for clarity:

Say I have arrays

A = { a1, a2 }, B = { b1, b2 }, C = { c1 }

I want to enumerate all the sets containing exactly one ax, bx and cx

{ a1, b1, c1 }, { a1, b2, c1 }, { a2, b1, c1 }, { a2, b2, c1 }

I want to enumerate them in a random order. The naïve solution would be to enumerate them in an array, then shuffle this array. But the solution is huge and I don't want to store it explicitely in memory.

Suppose that you have arrays $A_1,\ldots,A_d$ of sizes $n_1,\ldots,n_d$. The total number of tuples is thus $n_1 \times \cdots \times n_d$. Given a number in the range $1,\ldots,n_1 \times \cdots \times n_d$, you can decipher it into a tuple (I leave this part to you). It now remains to compute a pseudorandom permutation of the numbers $1,\ldots,n_1 \times \cdots \times n_d$, another task I leave to you.


Number of states in minimal Non Deterministic Finite Automata What will be the number of states in minimal NFA that can be designed
  to accept the language $L = \left \{ \epsilon  \right \}$ having a non
  empty alphabet set?

My friends are saying that this can be done using $1$ state, make the only state start state & final state without any transitions.

But will not this NFA accept every string over the alphabet set?
Because for every input string we are already in accepting state.
So every string will be accepted.
My claim is that at least $2$ states will be required so that we can get away from that default accepting state (start state) on any non empty string and the minimal NFA will be exactly same as the minimal DFA accepting $L$.

Am I correct?

But will not this NFA accept every string over the alphabet set?

It will not accept any strings except the empty one.
Since there are no transitions, the transition function $\delta(q_0,a) = \emptyset$ for all symbols $a$ of the input alphabet $\Sigma$, thus the extended transition function $\hat{\delta}(q_0,s) = \emptyset$ for all non-empty strings over $\Sigma$.

The set of accepting states $\{q_0\}$ and $\hat{\delta}(q_0,s)$ for all non-empty strings $s$ are disjoint, hence the NFA doesn't accept any non-empty strings.

As you already know this NFA accepts the empty string, and we just showed that it accepts only the empty string.

Remark: if it was a deterministic automaton you'd need 2 states to do the same thing. You could "cheat" and not show the 'dead state', but still it would be a 2 state DFA. With NFAs rules are a little bit different, since instead of states you use sets of states and having your NFA in no state at all (the empty set of states) is perfectly normal abstraction.


Context Free Grammar for $\{0^n1^n \mid n \geq 0\}^*$ Give a context free grammar for the following language over $\Sigma = \{0,1\}$:
  $ L = L_1^* $
  where $ L_1 = \{0^n1^n : n \geq 0\}$.

Not really sure where to start with this one. Any help is appreciated

Hints:

Start with a context-free grammar for $L_1$.
Modify it to a context-free grammar for $L = L_1^*$. There is a simple transformation which works for any context-free language $L_1$ and any context-free grammar generating it.


How does an automaton model a computer or something else? An automaton, as I have seen so far, is used to tell if a string belongs to the language that the automaton recognizes. This is determined by the final state of the automaton running on the string as an input. I wonder what role the output of the automaton plays here for this decision problem?
I saw that an automaton (e.g. a Turing machine) can  model a computer. A computer takes  a program (which can solve any problem, such as evaluating a function, optimizing a function, searching for something, ...)as an input, and outputs what the program asks the computer to do. So  when an automaton models a computer, what do the inputs, outputs, states and transition/output rules of the automaton represent?
Some also said that an automaton models an algorithm.
My understanding is that an algorithm is informally a sequence of instructions ( I can't find  the formal definition for an algorithm, and wonder what it is), while an automaton  has a set of rules for transition and output. So I wonder how to understand that an automaton models an algorithm?

1 seems to be just a special case of 2, since the decision problem is just a kind of problem that a computer can solve.

Regarding 2 and 3, if an automaton models a computer and a program is  its input, since a program represents an algorithm,  isn't an algorithm an input to an automaton instead? Thanks.

The impetus behind all of this comes from trying to define a mathematically rigorous model of what "computation" means. Alan Turing did this in 1936 by defining a definition of a simple abstract machine that seemed to be sufficient to describe everything that we'd call computation, a device we now call a Turing Machine.

Over the years, people have investigated other models of computation that were restricted in what they could do and discovered that these simpler models were also interesting in themselves. This eventually lead to what we might call the standard introduction to computability theory, as follows.

Finite Automata. Starting with this model, we have a finite collection of states and define transitions from one state to another depending on the current character being read in an input string. Some of these states are designated as final states and the convention is that if the automaton is in a final state after reading all the characters of the input, we say that the automaton accepts the input string.

(Important Digression): Languages and problems. Starting with a machine that can determine whether a string is or is not in a particular language, we can transform this task into a task of solving a problem. For instance, we might want to solve the problem "given nonnegative integers $n$ and $m$ are they both even or both odd?" It's not hard to see that this is equivalent to "can we make a finite automaton that accepts all and only strings in the language $L_1=\{a^nb^m \mid a\equiv b\pmod 2\}$, where $a^nb^m$ is the string of $n$ copies of $a$ followed by $m$ copies of $b$. It turns out that a finite automaton can be built to do this. The point here is that any computational problem can be turned into a language recognition problem, where the language is effectively an encoding of the possible solutions. In other words, the language
$$
\{(0, 0), (0, 2), (0, 4),\dots, (2, 0), (2, 4), \dots, (1, 1), (1, 3), \dots,\}
$$
can, suitably coded, be recognized by a FA

Other Automata. It happens that finite automata can't recognize solutions to all problems. For example, a FA (finite automaton) can't recognize the language $L_2=\{a^nb^n\mid n\ge 0\}$, in other words, it isn't powerful enough to determine whether two nonnegative integers $n, m$ are equal. If we modify our FA model by including a stack where we can push or pop symbols depending on the input string (as well as change to another state), then this new model (a pushdown automaton or PDA, as it's known) can recognize the language $L_2$ and also the language $L_3=\{a^nb^mc^{n+m}\}$, so a PDA can determine whether two numbers sum to another. It happens, though, that PDAs aren't powerful enough to do the same for products. We can continue this process, adding enhancements to each abstract model of computation, and get a hierarchy of increasingly more powerful machines. The exciting part is that this hierarchy quickly comes to an end.

Turing Machines. If we take a FA and add to it an arbitrary long list (called a tape) initially containing the input and allow moves where the current state and the current contents of an element in the list determine the next state, what we write in the current list element, and whether we move one position forward or backward in the list, we have Turing's 1936 abstract machine, a Turing Machine, or TM. This simple device is extremely powerful: it can add, subtract, multiply, divide, move data to a different location on the tape, compare two chunks of data and base its actions on the results of the comparison, and do things like compute prime numbers and give the $n$-th digit of $\pi$. In fact, it can do everything that modern computers can do and more, since, being an abstract machine, it has an arbitrarily large amount of "memory" on its tape, potentially vastly larger than the number of elementary particles in the universe.

Things to do With TMs. With this model, we can perform all the tasks we're used to:

Implement Functions. We can build a TM that, say, computes square roots: given two numbers on its tape, like "3.1416#7", we can define the moves of a TM to produce the square root of the input, 3.1416, to seven digits of precision, so at the end of its calculations, the tape would contain "1.7724559". This is just an algorithm: a finite sequence of steps in some model that produces a result according to our specifications.
Language recognizers (and problem solvers). We could design a TM that recognizes the language of primes: $L_4=\{2,3,5,7,11,13,17,19, \dots\}$: given an input tape initially containing an integer $P$, this machine could determine if $P\in L_4$, namely if $P$ is the decimal representation of a prime number.
Programmable Computers. It's even possible to design a universal TM which takes a suitably coded description of a TM, $\langle M\rangle$ (perhaps by a listing of its move rules), and an input $X$ and simulate the action of $M$ on input $x$, which of course exactly what a real-world computer plus compiler does.

Remarks and Consequences

Fully fleshed out, this narrative has a flow, from simple machines to, ultimately, a machine that's more powerful than any modern physical computer. The narrative doesn't stop there, though. The Church-Turing Thesis says that anything that we would agree falls under our definition of "computation" can be accomplished by a TM. In other words, the Church-Turing Thesis is a confident bet that not only are TMs more powerful than any modern computer, but that they can accomplish anything we'd call computation on any future computer.

It gets even better, though. Since the (uncountable) infinity of possible functions from the integers to themselves is vastly larger than the (countable) infinity of possible Turing Machines, it means that there are lots of tasks that TMs (and hence computers) cannot do. That might not be a real-world problem, since the functions that TMs can't compute are in a very real sense undescribable, but there are also plenty of seemingly programmable tasks that TMs (and hence computers) cannot do. For example, "given a listing of a program and an input for that program, can we always determine whether that program will eventually halt when given that input?" Professional programmers would love such a tool, but it is provably impossible to construct a program to determine, for all program listings and inputs, whether that program will perhaps enter an infinite loop or not. Similarly, there is no hope of determining, in all cases, whether a given program will behave according to some set of specifications. So our fascinating narrative has a sad ending: there are (infinitely many) tasks computers will never be able to do.


Are numbers types and what is "Number"? I was pondering about what are the numbers. It seems like a number is data type. I mean, like Maybe in Haskell. Because, for instance, one on its own means nothing for me. However, one apple tells me about how many apples does one talking about. Thus, numbers are quite abstract. If somebody asks you "how is it going" you can't answer "10". 10 what? But you could say 10 out of 10. But this is another abstraction. So, what I want to say is that a number is an abstraction. It can only be used to quantify other things. Thus, very often people say that "Number" is a type or set or category, etc. But then if a concrete number is an abstraction what is Number?

I hope you've got my idea and question and sorry if I used some terms incorrectly. I'm trying to study CS on my own and do make lots of mistakes.

So, you have to be very careful to distinguish values, and the types of those values.

We say $v : T$ when $v$ is a value with type $T$.

The type Number

When people say "Number" is a type, usually they're referring to the type of natural numbers. But each number isn't a type, it's a value, and $Number$ is their type. So we can say $1 : Number$, $2 : Number$, etc.

Notation isn't always consistent. Sometimes people will refer to $Number$ as a type class that contains $Nat, Int, Float$ etc. But that's more complicated.

Now, as for each number being a type, in a language like Haskell (or any Hindley-Milner lanugage), this isn't the case, because numbers are values, and types and values are separate.

But there are a few ways we can look at this

Numbers as singletons

But using dependent-types or GADTs, in a Haskell, Agda, Idris, or other languages with advanced types, you can form a type like this (using Agda-like pseudocode):

data TypeNat : Nat -> Set where
  TZero : TypeNat Zero
  TSucc : {n : Nat} -> TypeNat n -> TypeNat (Succ n)

For any number n, TypeNat n is a type, containing exactly one value, the TypeNat representation of n.

So here, the number isn't the type, but there's a 1:1 correspondence between the numbers and the types.

Numbers to Quantify other things

We can use numbers to quantify things, but in a dependent-type system, usually this is done by indexing types.

So you can have a type like Vec a n, which is the type of Vectors containing exactly n elements of type a. So here, our types are indexed by numbers, but the number itself is not a type.


no of times partion is called in quick sort, assuming array is always halved In the most even possible split, PARTITION function produces two subarrays, each of size no more than n/2. since one is of size floor(n/2) and one of size ceil(n/2)-1.
The recurrence for the running time will be,
$$
T(n) = 2T(n/2) + \Theta(n)
$$
where we tolerate the sloppiness from ignoring the floor and ceiling and from subtracting 1. By case 2 of the master theorem, this recurrence will have the solution
$$
T(n) = \Theta(n \log n)
$$
My Implementation is as follows:
QUICKSORT(A, p, r)
  if p < r
  q = PARTITION(A, p, r)
  QUICKSORT(A, p, q-1)
  QUICKSORT(A, q+1, r)

PARTITION(A, p, r)
  x = A[r]
  i = p - 1
  for j = p to (r - 1)
      if A[j] <= x
          i = i + 1
          exchange A[i] with A[j]
  exchange A[i+1] with A[r]
  return i + 1

Assuming that the array is always divided into 2 equal halves, how many times is the partition algorithm will be called?

The number of times the partition algorithm is called does not actually depend on where the array is partitioned (asymptotically).
To count the number of partitions you just need to count the number of internal nodes in the recursion tree. Since each internal node has at least two children, the recursion tree is a full binary tree. In a full binary tree, the number of leaves and internal nodes are linearly related (see this link). So the number of internal nodes would be $\Theta(n)$, no matter where the partition happens. You can easily prove this using induction on the number of nodes in the tree.


Short certificate analogy of PH? We know that for problems in NP if the problem is an yes version then there is a short certificate and for coNP if the problem is a no version then there is a short certificate.

Is there a short certficate analogy for higher levels in Polynomial Hierarchy?

The correct analogy for higher levels of the polynomial hierarchy is that of a game between two players, the $\exists$ player and the $\forall$ player. The $\exists$ player wants to prove that the input is in the language, and the $\forall$ player wants to disprove it.

For a language $L \in \Sigma_k^P$, the game is as follows. On input $x$, the $\exists$ and $\forall$ players alternate in presenting strings $y_1,y_2,\ldots,y_k$ (the $\exists$ player starts). After $k$ rounds, the referee runs a polynomial time procedure $f$ (set in advance) on $x,y_1,\ldots,y_k$, and declares $\exists$ to be the winner if $f$ returns YES, and $\forall$ to be the winner if $f$ returns NO. Since $L \in \Sigma_k^P$, when $x \in L$, $\exists$ has a winning strategy, and when $x \notin L$, $\forall$ has a winning strategy.

For a language $L \in \Pi_k^P$, the only difference is that $\forall$ starts.

When $k = 1$, there is no communication, and so we can talk in terms of witnesses. For larger $k$, we can still use the witness terminology, but with different semantics. Consider again $\Sigma_k^P$, for $k = 2r$ or $k = 2r+1$. The witness of $\exists$ consists of $r$ functions $Y_1,Y_2,\ldots,Y_r$ which are used to generate the strings produced by $\exists$ as follows: $y_1 = Y_1(x)$; $y_3 = Y_2(x,y_1,y_2)$ (or $y_3 = Y_2(x,y_2)$, since $y_1$ is known); and so on. You can think of these functions as implicit witnesses, since $\exists$ doesn't reveal the entire functions $Y_2,\ldots,Y_r$, but only the relevant values.

For $x \in L$, the property that these witnesses satisfy is that for any reply by the $\forall$ player, the referee declares $\exists$ to be the winner. For $x \notin L$, the $\forall$ player has a similar kind of witness. Thus "witness" here is really the same as a winning strategy.


How to write regular expression excluding certain pattern aba from albhabet set {a,b}? Often we are asked to write regular expression for the set of words that contain a certain string pattern, like $aba$. But what about the opposite?
Is there any generic way to write a regular expression for the set of all words that do not contain a certain pattern?

Maybe the easiest (though not necessarily fastest, if done by hand) way to do this is to make use of the many equivalent formalisms for regular languages:

Create an NFA that accepts all words that contain the pattern. (This NFA will consist of a chain of transitions that are labeled with the pattern and additionally can loop in the initial or final state on every symbol.)
Transform that NFA into a (complete) DFA using a standard algorithm.
Make all the accepting states of the DFA non-accepting and vice versa.
Translate the inverted DFA into a RE using a standard algorithm.


CFG for palindromes containing atleast 3 c's Input alphabet = {a,b,c}

I tried with the following grammar :-

S -> aSa / bSb / T
T -> cTc / cSc / cBc
B -> c  / cXc
X -> a / b / aXa / bXb / epsilon

This grammar is not able to generate 'cacac' .Is there any way to write this grammar with less number of productions or are any productions redundant here ?

Thanks.

You have a symbol S that needs to generate a palindrome with at least 3 c's.
Create a symbol X that needs to generate a palindrome with at least 1 c, and a symbol Y that needs to generate a palindrome with no requirement for c's.

S -> aSa | bSb | cXc
X -> aXa | bXb | cYc | c
Y -> aYa | bYb | cYc | a | b | c | eps

I think the essential step was not to start writing down productions, but to write down which different symbols you need to produce which kinds of output. The productions are then trivial.


How can I use the NP complexity Venn diagram to quickly see which class of NP problem can be poly reducible to another class? I'm so bad at solving the problem of the type:

  "If $A$ is an NP-complete problem, $B$ is reducible to $A$, then $B$ is..."

That I have to come here and ask these silly questions each and every time I encounter them.

Is there a good way of using the Venn Diagram shown below to tackle these kind of problem?

For example, how can I prove that If $A$ is an NP-complete problem, $B$ is reducible to $A$, then $B$ can be NP-hard using the above diagram?

If not possible, what would be another way to drill this into my head?

As Raphael said the definitions are important, especially if you try to create proofs. These definitions are not always captured in the Venn diagram.

The definition of NP-complete is not made clear from the diagram and will not help you to reason about

  "If A is an NP-complete problem, $B$ is reducible to $A$, then $B$ is...".

You cannot see from the diagram that this must mean that $B$ is NP.

To answer your question if it is not possible how you will be able to drill it into your head is much more complicated. But again the first step needs to be the definitions.

If you know that NP-completeness implies two properties of $A$ by definition, then you can take the next step.

  What does $B$ reducible to $A$ means when regarding these two properties. Do the properties of $A$ tell anything about $B$?

The second property says that any problem in NP reduces to $A$ in polynomial time. So if $B$ reduce to $A$ in polynomial time then $B$ is in NP.


Polynomial time problems with provably high degree time complexity? For any integer $k$, does there exist a decision problem in $\textbf P$ that can be proven to require $\Omega(n^k)$ steps?

The time hierarchy theorem, proved by diagonalization, shows that for every reasonable function $f$ there exists a problem solvable in $O(f(n))$ but not in $o(f(n)/\log f(n))$. One such problem is, given a Turing machine and in input $x$, to determine whether the machine halts in $x$ within $f(|x|)$ steps. In your case, you can choose $f(n) = n^k \log n$ to obtain a problem solvable in $O(n^k \log n)$ but not in $o(n^k)$.


in a graph G= (V,E), finding a clique of size |V|- d where d is some constant Is the question above still NP? I've been stuck on this question for couple of days now... I know k-Clique problem is NP-complete generally, but the problem is k = |V|-d where d is some integer constant...My current guess is that for large |V|,
d << |V| => Finding all subsets of size k = (V choose V-d) so this question is in P.

The brute force algorithm would check all vertex subsets of size $n-d$, where $|V|=n$. There are $$\binom{n}{n-d} = \binom{n}{d}=\frac{n(n-1)\dots (n-d+1)}{d!}$$ different subsets. This quantity is $\mathcal{O}(n^d)$ and since $d$ is constant this problem is in $P$.

You are asking

  Is the question above still NP?

Even though the problem is in $P$, this problem is still in $NP$ since $P \subseteq NP$, however, unlike $k$-clique problem this problem  may not be NP-complete.


Is there a method to generate the complement of a context-free grammar? Given the languages $L_0 = {w \in \{0,1\}^*}$ such that $w$ is a palindrome and $L_1 = {w \in \{0,1\}^*}$ such that $w$ is not a palindrome, meaning $L_1$ is the complement of $L_0$, we want to find the grammar for both languages. $G(L_0) = S \to \epsilon | 0S0 | 1S1 | 0 | 1$ is easy to come up with, but $G(L_1)$ is much more complex.
In this case, we have the simple CFG $G_0$ and want to find the CFG $G_1$ that is its complement which can be much more complex. Is there a method to derive the complement of a CFG?

If $L_0$ in a context-free language, this doesn't guarantee that its complement is context free. For example, consider the language
$$L_0 = \{a,b,c\}^* \setminus \{a^nb^nc^n : n \geq 0\}.$$
This language is context-free, but is complement (with respect to $\{a,b,c\}$) is not.
Another way to formulate your question is as follows: given a context-free grammar for a language $L$, is there an algorithm that either constructs a context-free grammar for the complement of $L$, or determines that the complement of $L$ is not regular? Such an algorithm can be used to decide whether the complement of $L$ is context-free. However, this is undecidable, as we now show following Hendrik Jan's notes.
Recall that given a grammar $G$ over an alphabet $\Sigma$, it is undecidable whether $L(G) = \Sigma^*$. Let $\#$ be a new symbol, and construct a grammar for the language
$$ L = L_0 \# \Sigma^* \cup \Sigma^* \# L(G), $$
where $L_0$ is a context-free language whose complement is not context-free (if $|\Sigma| \geq 3$, we can use the one above, and if $|\Sigma| = 2$, we can encode $a,b,c$ as $a,ba,bba$; if $|\Sigma| = 1$ then it is easy to check whether $L(G) = \Sigma^*$). If $L(G) = \Sigma^*$ then $L=\Sigma^*\#\Sigma^*$, and so the complement of $L$ is context-free. Otherwise, suppose that $w \notin L(G)$. Then
$$ \overline{L} \cap \Sigma^* \# w = (\Sigma^* \setminus L_0) \# w, $$
which is not context-free, and so $\overline{L}$ itself is not context-free (since the context-free languages are closed under intersection with a regular language). This shows that $\overline{L}$ is context-free iff $L(G) = \Sigma^*$.
The problem of deciding whether $L(G) = \Sigma^*$ is actually not recursively enumerable. This means that there is no algorithm which, on input $G$, halts iff $L(G) = \Sigma^*$ (however, there is a simple algorithm that halts iff $L(G) \neq \Sigma^*$, namely go over all words in $\Sigma^*$ in parallel, and check whether each of them belongs to $L(G)$). Therefore there is no algorithm that, given a context-free grammar for a language $L$, halts iff the complement of $L$ is context-free.
In other words, even the following solution to your problem does not exist: an algorithm that attempts to construct a context-free grammar for the complement of the given context-free language, and either halts with the grammar, or never halts (if the complement is not context-free).


Prove that $H$ reduces to $H\varepsilon$ I have to prove that $H_\varepsilon = \{<M> \mid M\ \text{halts on input }\varepsilon\}$ reduces to $H$ (the halting problem).

I am very confused how to PROVE it, I mean it is clear that we can take a TM $M$ that decides $H$ and then build a TM $M\varepsilon$ that decides $H\varepsilon$ by taking the input $<M1>$ and simulating $M$ on input $(<M1>, \varepsilon)$, then accepting when $M$ accepts.

But how do I prove I can do that, how do I prove that this mapping from $H$ to $H_\varepsilon$ exists?

This can be done by hard-coding a pre-processing stage to paste down $x$ to the input tape, before actually running $M$ on $x$ as input.

So given an instance $<M,x>$ of HALTING, you transform $M$ to $M_x$ that submerges the input $x$ into its initial stage. This can be done efficiently.

For example, if $x=010$, then start from the starting state $q$ of $M_x$ at left-marker $\$$, it moves one step to the right, and changes to state $q_0$. Then, $M_x$ prints out $0$, moves the head one step to the right and changes to state $q_1$. Then, $M_x$ prints out $1$, moves the head one step to the right and changes to state $q_2$. Then, $M_x$ prints out $0$, moves the head one step to the right and changes to state $q_3$. Then, $M_x$ moves all the way left back to the left-marker $\$$. Then, $M_x$ changes to the very starting state $q_M$ of $M$ and passes the control to $M$. Now, $M$ receives $x$ as input on the tape.

The above behavior of $M_x$ should be coded as its transition table. The description of $M_x$ is the produced instance of $H_\varepsilon$.

Finally, $M$ halts on $x$ iff. $M_x$ halts on $\varepsilon$.


Count the unique subsequences I'm trying to count the number of subsequences of a long string.

e.g. BANANA -> B, A, N, BA, BN, AA, NN, NA, BAN, BAA, BNA, BNN, ANA, AAA, NAN, NNA, etc

There's the horribly inefficient way, which is to iterate all of the substrings and keep hash of some sort to keep track of the ones already seen. The size of the hash explodes with any non-trivial length strings, so I need to figure out something more efficient.  I tried dynamic programming, but could not find a good recursive formula.

This problem is originally from http://ahslaaks.users.cs.helsinki.fi/oh/, and they don't use the term "subsequences" when describing it.

Let the given string be $S$.  For a string $T$ that appears as a subsequence of $S$, we say that the list of positions $(x_1, \dots, x_{|T|})$ is an appearance of $T$ in $S$ if $S[x_1]S[x_2]\dots S[x_{|T|}] = T$.  The leftmost appearance of $T$ in $S$ is the unique one for which each position is minimal over corresponding positions in all appearances -- that is, $X$ is the leftmost appearance of $T$ in $S$ iff for all $1 \le i \le |T|$ and all appearances $Y$ of $T$ in $S$, $X[i] \le Y[i]$.  This leftmost appearance can be calculated with a simple greedy algorithm in which we loop through the characters of $T$, pairing each with the next available matching character in $S$.  Define $L(T)$ to be the last (rightmost) position in the leftmost appearance of $T$ in $S$.

Example: $S = abbaba$, $T = ba$.  The appearances of $T$ in $S$ are $(2, 4), (2, 6), (3, 4), (3, 6)$ and $(5, 6)$.  The unique leftmost appearance is $(2, 4)$, so $L(T) = 4$.

We say a subsequence $T$ of $S$ requires position $i$ of $S$ iff $L(T) = i$.  What this means is that $T$ is not a subsequence of $S[1 \dots i-1]$ -- the only ways to produce $T$ from $S$ involve including either the character at position $i$ in $S$, or some identical character further to the right.  The important thing to notice is that any subsequence $T$ of $S$ requires a unique position: the one given by by $L(T)$.  So if for each $1 \le i \le |S|$ we can count the number of subsequences of $T$ that require $i$, we can add these all up to obtain the total number of unique subsequences of $S$.

Let $r(i)$ be the number of subsequences of $S$ that require position $i$.  We can compute $r(i)$ by counting the total number of subsequences of $S$ that include position $i$ and end there, and then subtracting off the number of these subsequences that don't require $i$.  Calculating the number of subsequences that end at $i$ but don't require it is surprisingly easy to do, thanks to the following observation:

For every $1 \le j < i$ such that $S[j] = S[i]$, every subsequence that requires $j$ can be turned into an appearance of the same subsequence that ends at $i$ but doesn't require $i$ -- and there are no other subsequences that end at $i$ but don't require it.  (Specifically, we could remove the final character (taken from position $j$ of $S$) and append position $i$, and the appearance formed this way yields the same subsequence.)

So we have $r(i) = \sum_{1\le k<i} r(k) - \sum_{1\le j<i, S[j]=S[i]} r(j)$.

(The first summation is the number of subsequences we get by appending $S[i]$ to each of the unique subsequences we have already seen; the second subtracts off subsequences we have seen before.)

The first summation is easy to optimise: It's just a running total.  The second summation can also be optimised further by tracking, for each distinct character, the sum so far of unique subsequences ending with that character:

$r(0) \gets 1$
For $i$ from 1 to $|S|$:

$r(i) \gets t - u[S[i]]$
$t \gets t + r(i)$
$u[S[i]] \gets u[S[i]] + r(i)$

Summing $r(i)$ values as they are computed allows the answer to be computed in linear time.


How can I partition a graph such that as few edges as possible cross partition boundaries? The following problem appeared while trying to distribute a program over a cluster of computers:

Given an undirected graph $G=(V,E)$ and an integer $n$, partition the vertices of $G$ into $n$ partitions $V_i$ of about equal size such that the number of edges crossing partition boundaries is minimised.

You can imagine $V$ as being chunks of a data set with $E$ indicating which chunks are related to what other chunks. When the computer operates on a chunk $v\in V_i$, it needs to access chunks from all $w\sim_E v$ and the performance is better if as many $w$ as possible are in the same partition $V_i$. The chunks are all of equal size and it is important that each partition $V_i$ contains about the same amount of them.

How can I a) model and b) approximate a good solution for this problem?

Your problem is known as graph partition. Apart from $n$, the problem has a parameter $\epsilon \geq 0$, and it is required that each part have size at most $(1+\epsilon)|V|/n$. The Wikipedia article mentions several relevant algorithms. The case $n = 2$ is known as minimum bisection when the parts are required to be exactly equal, and this is a well-known special case.


Asymptotic Question - Determining average case runtime of linear search with summation formula My confusion arises when solving the average case. I thought that it would be: 1/n * (number of elements)

But in the solution, they do 1/n * (sum of all the elements). I know that this all goes down to N when in big-o notation but why are they summing all elements of the array and how did they get to just the sum formula? I ended up with the same answer but my thought process was different.

Question:
Consider linear search again. How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in Θ-notation? Justify your answers.

TextBook Answer

The average should look for (n + 1) / 2 elements

The worst case is n

Assuming equal probability of occurrence 1/n, average number of elements which need to be checked is 1/n * (1 + 2 + ... +n) = (n+1)/2. Running time is Θ(n)

Worst case, the element to search is dead last in the array. In that case n elements need to be searched. Running time is Θ(n)

So all are Θ (n).

Suppose that it can be any element of your array. You'll have to consider, for $ 1 <= i <= n $ , what will be the cost if the searched element were at position $i$. If the element were in first position, it would cost $1$ iteration, at second $2$ iterations, and so on. So, if it were at position $i$, it would cost $i$ iterations. In addition, we have $n$ elements, with same chances, so the average cost is the average of the costs that's we have calculated. That's why it's $(1 + 2 + ... + n) / n$.

If you know about probabilities, costs for each element represent a discrete probability distribution, and the average cost is the expected value.


Winning strategy for a given game on graphs The game goes as follows. Two players are playing a game, player 1 and player 2, in which the first player starts by naming a hero $h_1$, then player 2 responds with a villain $v_1$ who has played in a movie with $h_1$. Then player 1 responds with another hero $h_2$ who has played in a movie together with $v_1$, and so forth. Each hero and villain can be used at most once. The first player that can not name any character (available heroes/villains do not have a common film with the last choice of the other player), loses the game. Player 1 always starts the game.

The input is a set of heroes $H$, a set of villains $V$ ($|H| = |V| \geq 1$) and a family of movies $M$, where each movie is a set of heroes and villains who appeared in that movie.

The question is: Can you, based on $H$, $V$ and $M$, decide which player wins the game assuming both players are playing optimally?

Example:

Given the following data: the heroes are Iron Man, Captain America, Thor and Spider-Man. The villains are Whiplash, Ultron, Thanos and Vulture. The movies are Avengers: Infinity War (stars Iron Man, Captain America, Thor, Thanos and Spider-Man) and Spider-Man: Homecoming (stars Iron Man, Vulture and Spider-Man). Can you decide which player has the winning strategy?

My approach is to use maximum bipartite matching to find out which player has the winning strategy, because we can split the data in two sets, namely $H$ and $V$ and have relations between those two sets. The Hopcroft-Karp algorithm can take two of such sets and find out the maximum cardinality. Please correct me if I'm wrong: in the cases in which there is a perfect matching, player 2 wins and otherwise player 1 wins. Whenever there is a perfect matching, it means that player 2 has always had an answers to the hero that player 1 named.

How would you solve this? Is there a better, more efficient solution than some maximum bipartite matching.

The short answer is, Player two wins if and only if the corresponding graph admits a matching that "covers" the set $H$.

Here is a bit of explanation.

Your idea is almost right. However, the proof is not intuitive and you might miss some details which you need if it is a theoretical question or if you need to design the exact winning strategy and not only output the winning player.

So let us start with the part missing from your answer. Assume a given instance corresponds to a graph that admits a perfect matching. According to your strategy, Player 2 wins in this case which is right. Now assume the same instance is given with one more villain, or ten more villains or one thousand of them. Clearly, player two still wins since adding villains, regardless to how we assign them, only helps the second player. So your claim does not always hold. However, your answer is very close to my claim and have the same intuition. It is only missing a bit of formality.

Claim. Assuming both players are playing optimally, Player 1 wins if and only if, given an instance $I$, the corresponding graph does not admit a matching saturating the set $H$.

So what does that mean? A matching saturates a set of vertices $S$, if each vertex in $S$ is incident to a vertex in the matching.
Now we prove the claim. We show two winning strategies one for Player two when the graph admits a matching the saturates the set $H$ and one for Player two when the graph does not admit such a matching.

Proof. Now assume the graph admits such a matching. Let this matching be $M$. The strategy goes as follows. As long as Player one did not lose, for each choice $h \in H$ for Player one, choose $v \in V$ the vertex matched to $h$ in $M$.

The correctness follows directly from the fact that each vertex of Player two is unique and adjacent to the choice of Player one (due the properties of a matching). Intuitively, Player one will run out of moves at some point (possibly after choosing all heroes in the set $H$).

Now assuming the graph does not admit a matching saturating $H$, according to Hall's theorem, there is a subset $A \subseteq H$, such that $|N(A)| < A$. Choose such a set that is minimal inclusion-wise. We claim that there is a matching $M'$ that saturates $N(A)$. Assuming otherwise, again due to Hall, there is a subset $S \subseteq N(A)$ such that $|N(S)| < S$, but then removing $N(S) \cap A$ from $A$ and $S$ from $N(A)$ yields a subset of $A$ that also contradicts Hall's condition which forms a contradiction to the choice of $A$ to be minimal. Hence, there is a matching $M'$ that saturates $N(A)$.

Now the strategy goes as follow. Choose a vertex in $A$ that is not incident to any edge in $M$. Such a vertex exists since $|N(A)| < |A|$. Choose this vertex at first and for each choice $v \in V$ of player two, choose the vertex $h \in H$ matched to $v$ in $M'$.

Again, it is easy to see that Player two will run out of moves at some point (possibly after choosing all vertices in $N(A)$) and hence, Player one wins.


prove by induction that the complete recursion tree for computing the nth Fibonacci number has n leaves I have referenced this similar question: Prove correctness of recursive Fibonacci algorithm, using proof by induction

*Edit: my professor had a significant typo in this assignment, I have attempted to correct it.

I am trying to construct a proof by induction to show that the recursion tree for the nth fibonacci number would have exactly n Fib(n+1) leaves.

that is to say that the complete recursion tree generated by the function F(n), which returns the nth fibonacci number in the sequence, has the same number of leaves as the number returned by the F(n+1), the n+1st fibonacci number.

Edit:  The complete recursion tree for n = 5 would look like this

                         F(5)
                      /        \
                 F(4)           F(3)
                /   \          /    \
             F(3)   F(2)      F(2)  F(1)
            / \      /  \     /   \
         F(2) F(1) F(1) F(0) F(1)  F(0)
        /   \
     F(1)  F(0)

Apparently, the question is messed up. Either the original homework question is wrong or there is serious misunderstanding reading or copying the original homework question.

Here is the correct title and question, "How to prove the complete recursion tree for computing $F_n$ has $F_n$ leaves where $F_n$ is the $n$-th Fibonacci number?".
Here the Fibonacci sequence is defined classically by $F_1=1$, $F_2=1$ and $F_{n+1}=F_n + F_{n-1}$. Note that we exclude $F_0=0$.

The complete recursion tree for n = 5 would look like the following, where we have $5=F_5$ leaves.

                      F(5)
                    /      \
                 F(4)      F(3)
                 /  \      /  \
              F(3)  F(2) F(2) F(1)
              /  \
           F(2)  F(1)

The proposition $P(n)$ for $n\ge1$ is the complete recursion tree for computing $F_n$ has $F_n$ leaves. The base case $P(1)$ and $p(2)$ are true by definition. If we use strong induction, the induction hypothesis $IH(k)$ for $k\ge2$ is for all $n\le k$, $P(n)$ is true. It should be routine to prove $P(k+1)$ given $IH(k)$ is true.

The main point of this answer is to point out the number of leaves in the complete recursion tree for computing $F_n$, the $n$-th Fibonacci number should be $F_n$ if $F_0=0$ is not in the definition of Fibonacci sequence.  Or it should be $F_{n+1}$ if $F_0=0$ is included in the base case and $F_2$ is not included in the base case.

Here is an easy exercise to describe the general situation.

Exercise. Let $S_1, S_2, \cdots$ be a sequence defined by $S_1=a$, $S_2=b$, $S_{n+1}=S_{n}+S_{n-1}$ for some $a$ and $b$. Show that the complete recursion tree to compute $S_n$ has $F_n$ leaves, where $F_n$ is the $n$-th Fibonacci number.


Sort Algorithm running in O(n) An array A holds n integers, and all integers in A belong to the set {0,1,2}. Describe an O(n) sorting algorithm for putting A in sorted order.
Your algorithm may not make use of auxiliary storage such as arrays or hash tables. More precisely, the only additional space used, beyond the given array is O(1). Give an argument to explain why your algorithm runs in O(n) time.

This is a self-answered question, but other answers are certainly desired.

My answer was the following:

 Algorithm Sort(A, n)
   Input: an array A of n integers, the element of A belong to the set {0,1,2}
   Output: A is sorted
   int zero ← 0, one ← 0
    for i = 0 to n-1
    // we count the number of occurrences of each element in the array
    switch(A[i])
      case 0:
        zero ← zero + 1
      case 1:
        one ← one + 1
    // 2 would be be n - ( zero + one)
    // now we populate the array
    for i = 0 to n – 1{
      if i < zero then A[i]  = 0
      else if i < zero + 1 then A[i] = 1
      else A[i] = 2

The algorithm traverses the array twice, so its execution time is at least 2n.
I was thinking of a way to get rid of the second for loop, but I doubt it can be avoided, unless the input array is already sorted or it contains element of the same type.
In any case 2n is O(n).


Parsing arbitrary context-free grammars, mostly short snippets I want to parse user-defined domain specific languages. These languages are typically close to mathematical notations (I am not parsing a natural language). Users define their DSL in a BNF notation, like this:

expr ::= LiteralInteger
       | ( expr )
       | expr + expr
       | expr * expr

Input like 1 + ( 2 * 3 ) must be accepted, while input like 1 + must be rejected as incorrect, and input like 1 + 2 * 3 must be rejected as ambiguous.

A central difficulty here is coping with ambiguous grammars in a user-friendly way. Restricting the grammar to be unambiguous is not an option: that's the way the language is — the idea is that writers prefer to omit parentheses when they are not necessary to avoid ambiguity. As long as an expression isn't ambiguous, I need to parse it, and if it isn't, I need to reject it.

My parser must work on any context-free grammar, even ambiguous ones, and must accept all unambiguous input. I need the parse tree for all accepted input. For invalid or ambiguous input, I ideally want good error messages, but to start with I'll take what I can get.

I will typically invoke the parser on relatively short inputs, with the occasional longer input. So the asymptotically faster algorithm may not be the best choice. I would like to optimize for a distribution of around 80% inputs less than 20 symbols long, 19% between 20 and 50 symbols, and 1% rare longer inputs. Speed for invalid inputs is not a major concern. Furthermore, I expect a modification of the DSL around every 1000 to 100000 inputs; I can spend a couple of seconds preprocessing my grammar, not a couple of minutes.

What parsing algorithm(s) should I investigate, given my typical input sizes? Should error reporting be a factor in my selection, or should I concentrate on parsing unambiguous inputs and possibly run a completely separate, slower parser to provide error feedback?

(In the project where I needed that (a while back), I used CYK, which wasn't too hard to implement and worked adequately for my input sizes but didn't produce very nice errors.)

Probably the ideal algorithm for your needs is Generalized LL parsing, or GLL. This is a very new algorithm (the paper was published in 2010). In a way, it is the Earley algorithm augmented with a graph structured stack (GSS), and using LL(1) lookahead.

The algorithm is quite similar to plain old LL(1), except that it doesn't reject grammars if they are not LL(1): it just tries out all possible LL(1) parses. It uses a directed graph for every point in the parse, which means that if a parse state is encountered that has been dealt with before, it simply merges these two vertices. This makes it suitable for even left-recursive grammars, unlike LL. For exact details on its inner workings, read the paper (it's quite a readable paper, though the label soup requires some perseverance).

The algorithm has a number of clear advantages relevant to your needs over the other general parsing algorithms (that I know of). Firstly, implementation is very easy: I think only Earley is easier to implement. Secondly, performance is quite good: in fact, it becomes just as fast as LL(1) on grammars that are LL(1). Thirdly, recovering the parse is quite easy, and checking whether there is more than one possible parse is as well.

The main advantage GLL has is that it is based on LL(1) and is therefore very easy to understand and debug, when implementing, when designing grammars as well as when parsing inputs. Furthermore, it also makes error handling easier: you know exactly where possible parses stranded and how they might have continued. You can easily give the possible parses at the point of the error and, say, the last 3 points where parses stranded. You might instead opt to try to recover from the error, and mark the production that the parse that got the furthest was working on as 'complete' for that parse, and see if parsing can continue after that (say someone forgot a parenthesis). You could even do that for, say, the 5 parses that got the furthest.

The only downside to the algorithm is that it's new, which means there are no well-established implementations readily available. This may not be a problem to you - I've implemented the algorithm myself, and it was quite easy to do.


Proving that no finite automaton can recognize a Dyck language I was reading up on finite automata and I came across an interesting fact near the end of the Wikipedia page.

  The classic example of a simply described language that no DFA can
  recognize is bracket or Dyck language, i.e., the language that
  consists of properly paired brackets such as word "(()())".
  Intuitively, no DFA can recognize the Dyck language because DFAs are
  not capable of counting: [...]

Although it is very intuitive the argument they gave, I was wondering if there were a formal proof I could read for this, or if simple enough, reconstruct.

I tried Googling around for a proof, but I think I am missing some sort of a keyword in my search because nothing useful is coming up, it this proof trivial or intuitive enough that no papers have been published on it?

Consider a Dyck language $L$ with $k$ types of parentheses, one of them $()$. If $L$ were regular then $L \cap (^*)^*$ would be regular, but this is just the well-known non-regular language $a^nb^n$ (with $a,b$ replaced by $(,)$).

There are many ways to prove that $L' = \{a^nb^n : n \geq 0\}$ isn't regular. Here is one. Suppose that $A$ is a DFA recognizing $L'$, with states $Q$, initial state $q_0$, accepting states $F$, and transition function $\delta$. Let $q(i) = \delta(q_0,a^i)$. If $i < j$ then $q(i) \neq q(j)$, since otherwise $\delta(q_0,a^ib^i) = \delta(q_0,a^jb_i)$ although the former is in $F$ while the latter isn't. This implies the absurd conclusion that $Q$ must be infinite.


Condensed Nearest Neighbor Explanation I have a question regarding the Condensed Nearest Neighbor algorithm from “Nonparametric Methods.” Introduction to Machine Learning (OIP), by Ethem Alpaydin, Mit Press, 2004, pp. 174–174:
! [“Nonparametric Methods.” Introduction to Machine Learning (OIP), by Ethem Alpaydin, Mit Press, 2004, pp. 174–174.]1

Ultimately, I am supposed to return the subset Z to be a local minimal subset to use for training set in KNN. Why am I returning Z, which, if I understand correctly, is the array of all of the misclassified points? Wouldn't I want to return the points that were classified correctly? What benefit does this give me in returning all the points I got wrong?

Z is not the array of misclassified points.  Try working through an example, and be careful and precise when making statements like that; while you can talk about which points are classified by a particular classifier, that will depend on the classifier.  So, when there are multiple classifiers floating around (or multiple training sets floating around), you need to specify which classifier you are referring to.  I suspect this is what is tripping you up: something that is misclassified with one training set might be correctly classified with another training set.

The key guarantee of this procedure is: if you use Z as your training set for a nearest-neighbor classifier, then this NN classifier will have 100% accuracy.  Try working through an example to see why.  (It iteratively grows the training set as needed to ensure that every point will be classified correctly by that NN classifier.)

As always, when you are confused, start by working through a small example with a few points (two, three, four), simulating the algorithm by hand, with pencil and paper.  That will often be very effective at building intuition -- and in this case it should be sufficient to understand what is going on.


Summing $1,3,5,\ldots$ I solved a recurrence to get the formula $T(n) = \sum_{i=1}^{k}2i+1$ for $k = \frac{n-1}{2}$, namely

$$ T(n) = 1 + 3 + \dots + (n-4) + (n-2) + n, $$

but I'm not sure how to finish off the problem by writing the summation and solving for the complexity.


Recurrence relation of quicksort depending on its pivot I understand how the recurrence relation of quicksort is

$T(n) = 2T(n/2)+\mathcal{O}(n)$,

but if we are guaranteed a certain pivot, for example $n/4$th smallest element to be the pivot every time, how would it affect the recurrence relation? I would love some insight on how to approach analyzing such performance.

When the 4th smallest element is always chosen as a pivot then the recurrence relation is
$$T(n) = T(n/4)+T(3n/4) + \mathcal{O}(n).$$

If we look at the recursion tree we will see that the left branch has $\log_4 n$ depth and the right has $\log_{4/3} n$ depth. At each step, until the leftmost branch terminates, the sum of levels is equal to $cn \in \mathcal{O}(n)$, for the remaining the levels the sum $\leq cn$. Therefore in the worst case calculation, if we assume all have depth $\log_{4/3} n$ and have $cn$ cost then the cost is;

$$c n \log_{4/3} \in \mathcal{O}(n\log n)$$


Which would be the most purely functional equivalent to generators? Some programming languages, apart from functions, have generators (eg. Python's yield). Although generators are introduced in this Python's tutorial on functional programming, I don't think that they can be considered functional programming, because they do have state, and in a vary implicit manner.

Generators are reminiscent of laziness in pure functional languages like Haskell. Apart from laziness, are there other purely functional alternatives for having a construct similar to generators? Do you have any examples?

Functional programming does not have to be pure or stateless.  There's no strict rule.  Languages that are designed to support first-class functions and higher-order functions can still be considered functional languages.  For instance, Standard ML has support for mutable variables but is still considered a functional language.

Also, functional programming can be considered a style of organizing your program rather than a property of a programming language.  So, it is possible to use Python in a functional way.

A Python generator can be written in a way so that it is purely functional: e.g., it produces a lazy list/stream and operates in a purely functional way.  Internally, generators might be implemented in a way that involves state, but from the outside (from the perspective of code that invokes a generator), I think it is possible to write the generator so it behaves in an observationally pure way (i.e., observationally indistinguishable from pure).

I'm not sure what you mean by "purely functional alternatives for having a construct similar to generators" so I don't know how to answer that part.


Hamming and BCH codes Why are Hamming codes the best 1-error-correcting codes?
I need references. I know that hamming codes are the best 1-error-correcting codes but I want to know why they are best?

The Hamming codes are optimal in the sense that among all codes with the same block length and minimal distance, they contain the most number of codewords. We know this because Hamming codes are perfect codes: their number of codewords matches the Hamming bound, which is an upper bound on the number of codewords in a code with given block length and minimal distance.


Is it possible for the runtime and input size in an algorithm to be inversely related? I'm wondering if it's possible for algorithms that have monotonically decreasing runtime with the input-size - just as a fun mental exercise. If not, is it possible to disprove this claim? I haven't been able to come up with an example or counterexample so far, and this sounds like an interesting problem.
P.S. Something like $O(\frac{1}{n})$, I guess (if it exists)

Try brute force searching of a key for a cryptographic algorithm.  The more of the key you give it to start with, the less you have to search for.  True that trend stops at the limit of keysize (but that's still monotonic), and there are probably other examples in the field of extensive search where the more input data, the easier it is to prune branches of the potential tree.


Approximation ratio when optimal solution is $0$ This might be a basic technicality but I'd like to make sure how to handle it.
The question is: how do we measure an algorithm's approximation (multiplicative) factor on instances with optimal value $0$.

Suppose I have a minimization problem $Pb$, and it is NP-Hard to decide if a given instance $I$ has optimal value $OPT(I) = 0$.

As a concrete example, say that $Pb$ is the problem of removing a minimum number of edges from a graph so that it is $3$-colorable.  Deciding if $0$ edges suffice is NP-hard.

Suppose now that I have an approximation algorithm $A$ for $Pb$ that runs in polynomial time.  How could $A$ achieve any kind of approximation factor?
Suppose $A$ always finds a solution of value $APP(I)$ within factor $\alpha$.  Then on instances of value $0$ it must return a value $APP(I) \leq \alpha \cdot OPT(I) = 0$.  Thus $APP(I)$ decides whether $OPT(I) = 0$.  Unless $P = NP$, this is impossible and so $A$ cannot approximate $Pb$ within any factor in polynomial time, let it be constant, $poly(n)$, superexponential in $n$, whatever...

Is that it?  Or is there some way around this technicality?

That's right.  Such a problem is not approximable to within any constant factor large than 1 (unless P=NP).

Is there a way around this?  Yes, there are several possibilities:

Use a different measure of approximation, rather than multiplicative factor.  For instance, you could consider its additive approximability.
Re-define the problem so it cannot have output of 0.  For instance, let $Pc(G)=Pb(G)+1$, i.e., $Pc$ is the problem of computing the minimum number of edges to remove from a graph so it becomes 3-colorable, plus one.  Then there is no such barrier to achieving some constant approximation factor. (There might still be other barriers, of course.)  Suppose you found that $Pc$ has a 2-approximation.  Then you could unfold what that implies for $Pb$.


MST: Prim's algorithm complexity, why not $O(EV \lg V)$? According to CLRS, the Prim's algorithms is implemented as below --

  $\mathtt{\text{MST-PRIM}}(G,w,r)$

  for each $u \in V[G]$ do

  $\mathtt{\text{key}}[u] \leftarrow \infty$
  $\pi[u] \leftarrow \mathtt{\text{NIL}}$

  $\mathtt{\text{key}}[r] \leftarrow 0$
  $Q \leftarrow V[G]$
  while $Q \ne \emptyset$ do // ... $O(V)$

  $u$ $\leftarrow$ $\mathtt{\text{EXTRACT-MIN}}(u)$ // ... $O(\lg V)$

  for each $v \in \mathtt{\text{adj}}[u]$ do // ... $O(E)$

  if $v \in Q$ and $w(u,v) \gt \mathtt{\text{key}}[v]$

  then $\pi[v] \leftarrow u$

  $\mathtt{\text{key}} \leftarrow w(u,v)$ // $\mathtt{\text{DECREASE-KEY}}$ ... $O(\lg V)$

The book says the total complexity is $O(V \lg V + E \lg V) \approx O(E \lg V)$. However, what I understood is that the inner for loop with the DECREASE-KEY operation will cost $O(E \lg V)$, and the outer while loop encloses both the EXTRACT-MIN and the inner for loop, so the total complexity should be $O(V (\lg V + E \lg V)) = O(V \lg V + EV \lg V) \approx O(EV \lg V)$.

Why the complexity analysis is not performed as such? and What is wrong with my formulation?

The complexity is derived as follows. The initialization phase costs $O(V)$. The $while$ loop is executed $\left| V \right|$ times. The $for$ loop nested within the $while$ loop is executed $degree(u)$ times. Finally, the handshaking lemma implies that there are $\Theta(E)$ implicit DECREASE-KEY’s. Therefore, the complexity is: $\Theta(V)* T_{EXTRACT-MIN} + \Theta(E) * T_{DECREASE-KEY}$.

The actual complexity depends on the data structure actually used in the algorithm.
Using an array, $T_{EXTRACT-MIN} = O(V), T_{DECREASE-KEY} = O(1)$, complexity is $O(V^2)$ in the worst case.

Using a binary heap, $T_{EXTRACT-MIN} = O(\log V), T_{DECREASE-KEY} = O(\log V)$, complexity is $O(E \log V)$ in the worst case. Here is why: since the graph is connected, then $\left| E \right| \ge \left| V \right| - 1$, and $E$ is at most $V^2$ (worst case, for a dense graph) . Probably, you missed this point.

Using a Fibonacci Heap,  $T_{EXTRACT-MIN} = O(\log V)$ amortized, $T_{DECREASE-KEY} = O(1)$ amortized, complexity is $O(E + V \log V)$ in the worst case.


Balanced based representation I'm interested in balanced base $B$ representation for fixed point arithmetic. The paper Fixed-point arithmetic in SHE schemes (Costache, Smart, Vivek and Waller, in Proceedings of 23rd International Conference on Selected Areas in Cryptography (SAC 2016), Springer Lecture Notes in Computer Science, vol. 10532, pp. 401–422, 2016; PDF) provides two examples using balanced based $B=3$. However, I don't understand the 2nd second representation, i.e.
$$\frac{8}{3}=10.\bar{1} $$
where $\bar{1}=-1$.
More generally speaking, I'm also interested in balanced form representation $B=5, 7$.
I believe this should be a well-known problem, though I was not able to google it. Do you know some relevant literature to this?

The expression $10.\overline{1}$ should be interpreted as follows:
$$
1 \cdot 3^1 + 0 \cdot 3^0 + (-1) \cdot 3^{-1} = 3 - \frac{1}{3} = \frac{8}{3}.
$$
The interpretation of balanced base $b=2d+1$ is the same, with the digits ranging from $-d$ to $d$.


help regarding combinatorics I want to know if there is any good book or material that fully explains and fully covers all combinatorics.I even did not find even Kenneth H.Rousan for this.So can anyone tell me any Discrete Mathematics book or any material to fully  explain Combinatorics even to advance level.that provide classification to combinatorics problems(most important).

You say in a comment:

  I am interested in combination problems that contain-distribution of distinct/indistinct objects to distinct/indistinct people,also with type of partition not defined,unordered partition etc advanced level problems

It doesn't sound to me like you want a book that covers all of combinatorics. Combinatorics is a vast subject, which includes enumerative combinatorics, probabilistic combinatorics, extremal combinatorics, graph theory, and several other subdisciplines. It sounds to me like you are interested in a subarea of enumerative combinatorics.

Richard Stanley's two-volume series on enumerative combinatorics is quite good, and I suspect it contains the material you want.


When does Gaussian elimination solve exact 1-in-3 SAT? Terms:

A literal is a variable or its negation.

A clause is a set of literals.

An exact 3-in-1 clause is satisfied if an assignment of values to variables results in exactly 1 true literal and 2 false literals.

Exact 3-in-1 SAT is the problem, given a set of exact 3-in-1 clauses, is there as assignment of variables that satisfies all clauses?

Question:

This corresponds to a linear algebra problem, sort of:

Let true be 1 and false be -1.

For each variable v and its negation w, add the equations:

v + w = 0

(This is because 1 + (-1) = 0)

For each exact 3-in-1 clause (a b c), add the equations:

a + b + c = -1

(This is because two -1's and one 1 will add up to -1.)

It's possible solving the equations results in a value other than 1 or -1. However if the solution to the system of equations is only 1 and -1, I suspect that's a valid solution to the original exact 1-in-3 problem.

So, when does Gaussian elimination solve exact 1-in-3 SAT?

Here's an example when it does:

These clauses:

(1 2 3)
(2 3 -2)
(2 3 -3)

Correspond to this matrix:

1, 0, 0, 1, 0, 0, 0
0, 1, 0, 0, 1, 0, 0
0, 0, 1, 0, 0, 1, 0
1, 1, 1, 0, 0, 0, -1
0, 1, 1, 0, 1, 0, -1
0, 1, 1, 0, 0, 1, -1

Reduced row echelon:

1, 0, 0, 0, 0, 0, 1
0, 1, 0, 0, 0, 0, -1
0, 0, 1, 0, 0, 0, -1
0, 0, 0, 1, 0, 0, -1
0, 0, 0, 0, 1, 0, 1
0, 0, 0, 0, 0, 1, 1

Therefore solution (via far-right column) is: (1 -2 -3)

Does this always work on larger matrices with 2*n rows and 2*n+1 columns where n is the number of variables? (I think it may need non-redundant (linearly independent?) rows.)

Does this always work on larger matrices with 2*n rows and 2*n+1 columns where n is the number of variables? (I think it may need non-redundant (linearly independent?) rows.)

It works but since there are assignments other than -1 and 1, how will you use the row echelon form to make any conclusions about the 1-in-3 SAT instance?

Two cases:

Case 1: The 1-in-3SAT formula is unsatisfiable but the reduced row echelon matrix is satisfiable (because of the possible assignments other than -1/1)
Case 2: Both are satisfiable but assigning a 1 and -1 may bring you back to Case 1

Therefore you will have to try an exponential number of assignments in worst case. Assigning random -1 and 1 values will force you to assign undesirable values during the end of elimination and you will have to backtrack.

If you find an algorithm to find "only the solutions with -1 and 1" or count such solutions or prove there are 0 then it is NP-complete and even co-NP complete.


Reduce variant of Vertex Cover to original decision-version Vertex cover problem Consider the following variation (let us call it Q) on the Vertex Cover problem: Given a Graph G and a number K, we are asked if there is a k-cover of G so that it is the minimum cover.
My question is: How may one prove that Q can be reduced to the general Vertex Cover problem?
And, more generally, what is the approach to solve such a reduction, from "is there a k..." to
"is k the minimum/maximum?"? I have a hunch on the methodology but am not sure and would appreciate a wiser opinion than that of myself on the subject.

My hunch is the following: First of all, we take into consideration the following fact:
if there is a k-1 cover of G, then we will surely have a k cover of G, just by adding a random node to the k-1 cover ( the cover property holds if we add nodes ). Thus, We can reformulate Q this way: Is there a k-cover of G, so that there is no (k-1)-cover of the graph? From this reformulation it is clear that an instance of Q reduces to 2 instances of the original decision version of the Vertex Cover.

Your reduction works. A more efficient version would be to use binary search to find the optimal value through a series of queries "Is there a vertex covers of size $k$?"

However, note that this is a polynomial-time Turing reduction (also known as a Cook reduction): you're solving the vertex cover optimization problem by making multiple queries to an oracle for the decision version. On the other hand, NP-completeness is defined in terms of polynomial-time many-one reductions (a.k.a. Karp reductions): here, you're only allowed to make one to the decision version.  I'm not aware of a many-one reduction between these two problems.

Cook reductions have the advantage that they correspond more closely to the idea of "If I have an efficient algorithm for problem A and a reduction from B to A, I have an efficient algorithm for B, too. On the other hand, Karp reductions allow for finer-grained distinctions in complexity theory. For example, there are Cook reductions between NP-complete problems and coNP-complete problems but a Karp reduction between an NP-complete problem and a coNP-complete problem would prove that NP=coNP.


Finding dynamic programming algorithm I got a matrix of integers of size $3\times n$. Of each one of the three rows, for each column I got to choose one number, with the restriction that, for each $i$, the numbers chosen in the $i$th and $(i+1)$st rows cannot come from the same column.

The problem asks to make an algorithm such that the summation of all the numbers I've chosen  is the minimum possible, has time complexity $O(n)$ and space complexity of $O(1)$.

I know how to do this with dynamic programming, in a more classical way: I calculate the sub-problems, store the results in a matrix of size $3\times n$ until the matrix is complete, then the result is the minimum value of the last row.

The problem is that will have space complexity of size $O(n)$, what I'm not seeing?

Run along the columns of the matrix keeping three numbers. For each row determine the minimum score assuming the last number chosen came from that row.


Mapping reduction from $A_{TM}$ to $INFINITE_{TM}$ same as to $ALL_{TM}$? I was trying to solve a problem with a mapping reduction from $A_{TM}$ to $INFINITE_{TM}$, and came across a solution that was 100% identical to another solution I saw for $A_{TM} \leq_M ALL_{TM}$. This is the reduction:

$M_f$: Given an input of $\langle M, w\rangle$, where $M$ is a $TM$ and $w$ is a word:

Define a TM $M_1$:

Given the input $x$ do:

Run $M$ on $w$ and return its result
Return $\langle M_1\rangle$

This is correct for $ALL_{TM}$ because if $M$ accepts $w$, $L(M_1)=\Sigma^*$, whereas if it rejects, $L(M_1)=\emptyset$

However, it is also given as a solution for $A_{TM} \leq_M INFINITE_{TM}$, where

$INFINITE_{TM}=\{\langle {M \rangle} |$ $M$ is a $TM$, $L(M)$ is an infinite language $\}$, for example here: http://www.sfu.ca/~kabanets/308/lectures/lec7.pdf

I don't fully understand why theirs, or other similar explanations, are correct. What about infinite languages that aren't $\Sigma^*$? What about finite languages that aren't $\emptyset$?

The m-reducibility definition says

Language $A$ is m-reducible to $B$ (denoted $A\leq_mB$) if there is a
computable function $f:\Sigma^* \rightarrow \Sigma^*$ such that for
every $w\in \Sigma^*$, $$w\in A \iff f(w)\in B$$

The point you should pay attention to is that there is no need to talk about every $x\in B$. If you can map all elements of $A$ to one special element of $B$ say $x_0$ and all strings that don't belong to $A$ to string which doesn't belong to $B$ say $y_0$ then you are done!
Maybe if you think of $A\leq_m B$ as language $B$ is harder than $A$ then you feel better about the reduction. This means if you can decide $B$ then you also can also decide $A$.
So by the proof, you have provided we map every $\langle M,w\rangle \in A_{TM}$ to $\Sigma^*$ and every $w' \notin A_{TM}$ to $\emptyset$. Thus $INFINITE_{TM}$ is harder than $A_{TM}$. If you could decide just one elements of $INIFINITE_{TM}$ which is $\langle M \rangle$ that $L(M)=\Sigma^*$ then you could decide $A_{TM}$.


Average-Case Analysis of a Simple Max-Finding Algorithm Given this piece of code:

FindMax(L):
   k = len(L) - 1
   max = L[k]
   k = k - 1
   while(k >= 0):
      if(L[k] > max):
         max = L[k]
      k = k - 1
   return max

How would you go about computing the average-case complexity with respect to the number of times $max$ is assigned? The way I've been taught to approach a question like this is to partition the sample space into events that could represent all possible inputs. But I'm having a hard time deciding what that partition should be

Don Knuth recently gave a recreation of his first lecture ever given at Stanford in which he addresses precisely this question with virtually the same code structure as what you have above. True to form, he showed up with a wig and authentic 1960's attire. You can watch a recording of that lecture online if you're interested.

Another way to derive this result is to use indicator variables. Let $X_i$ be an indicator variable that is 1 if the value of max changes on the iteration of the loop corresponding to a length-$i$ subarray and 0 otherwise. Assuming the permutation given as input is uniformly random, this variable is 1 with probability $\frac{1}{i}$ because max only changes if the inspected element is the largest of its group. Using linearity of expectation, you can use this to show that the number of updates on expectation is $\Theta(\log n)$. Knuth's talk gives a different perspective using generating functions and derives a precise value as well as the variance.


Decomposing the search problem into several small problems I am looking for papers/methods (or at least problem examples) where the original search problem $P$ can be solved by either:

Searching through the original graph. or
By decomposing it into several subset of problems $P_1,P_2, \dots,P_n$.

Ideally $sol(P )=sol(P_1)\cup sol(P_2)\cup \ldots \cup(P_n)$ with no preprocessing (i.e the union of the subproblems correspond directly to the solution of the problem).

I have no constraint; though prefer the underlying graph to be a DAG and the problem to be a reachability problem. Google seems to fail on finding such papers.

The term you are looking for is "divide-and-conquer".  There are gazillions of divide-and-conquer algorithms; any algorithm textbook should show you quite a few examples.  Divide-and-conquer is more general, because it also allows you to do some merger operation to combine the solutions to each piece -- but many divide-and-conquer algorithms do follow the form you are looking for, so I think "divide-and-conquer" should be a helpful search term.

In graphs, one common use of divide-and-conquer is to decompose the graph into connected components or strongly connected components, and then work on each component separately.  In many cases, no pre-processing or post-processing to glue together the solutions is needed: you just take a union of the solution for each component.


Solving recurrence relations with two variables I am trying to solve this recurrence relation with two variables:

$$T(n, k) = T(n - 1, k - 1) + T(n - 1, k)$$

The base cases are:

$T(n, k) = 1$ if $k = 0$
$T(n, k) = 0$ if $k > n$

I was wondering if standard techniques like characteristic polynomial and generating function would work in this situation.

The standard technique is to notice that your recurrence is just Pascal's identity, and so
$$
T(n,k) = \binom{n}{k}
$$
is a solution to the recurrence. There are other solutions, for example $T(n,k) = 2^n$, and multiples of both.

In your case, the binomial coefficient satisfies the initial conditions, so it is the solution.

Now, let's solve it using generating functions. Let
$$
f(x,y) = \sum_{n,k} T(n,k) x^n y^k.
$$
The initial conditions imply that $T(0,0) = 1$ and $T(0,k) = 0$ for $k > 0$. Also, $T(n,0) = 1$ for all $n$. Applying the recurrence for all $n,k>0$ and using these base cases, we get
$$
\begin{align*}
f(x,y) &= \sum_{n=0}^\infty x^n + \sum_{n,k>0} [T(n-1,k-1)+T(n-1,k)] x^n y^k \\ &=
\sum_{n=0}^\infty x^n + \sum_{n,k} T(n,k) x^{n+1} y^{k+1} + \sum_{\substack{n \geq 0\\k>0}} T(n,k) x^{n+1} y^k \\ &=
\sum_{n=0}^\infty x^n + xyf(x,y) + xf(x,y) - \sum_{n=0}^\infty x^{n+1} \\ &=
1 + (x+xy) f(x,y).
\end{align*}
$$
Therefore
$$
f(x,y) = \frac{1}{1-x-xy}.
$$
The coefficient of $x^n y^k$ is the number of walks that start at $(0,0)$, end at $(n,k)$, and at each step, either move right or diagonally. Clearly they have to move right exactly $n-k$ times (so if $n < k$ the coefficient is zero) and diagonally exactly $k$ times, but the order is not important. Therefore the number of walks is $\binom{(n-k)+k}{k} = \binom{n}{k}$.


Differences between Church and Scott encoding I'm kind of new to lambda calculus and I found this Wikipedia article
https://en.wikipedia.org/wiki/Mogensen%E2%80%93Scott_encoding

The section Comparison to the Church encoding presents a short comparison between Church and Scott encoding

Church

λx1...xAi.λc1...cN.ci (x1c1...cN)...(xAic1...cN)

Scott

λx1...xAi.λc1...cN.ci  x1...xAi

Do you agree with the Church generic encoding description? The page specified that citation is needed for that description.

It's correct as long as all the arguments $x_1 ... x_{A_i}$ are recursive occurrences of the same structure. Otherwise there's no way to say what the Church encoding should be without more information.

That is the major difference between the Church and Scott encodings. If we think in terms of types, then for a fixed point type:

$T \cong F T$

the Church encoding of $T$ has a type like:

$(F r \to r) \to r$

while the Scott encoding has a type like:

$(F T \to r) \to r$

So, Scott encodings generally require some other source of recursion/iteration, both at the value level, because it only gives you access to one level of unfolding at a time, and at the type level (if you have one), because the fixed point type $T$ is still present in the type of the Scott encoding.

However, this means that Scott encodings are much better than Church encodings for some things. For instance, it's obvious how to write the (clamped) predecessor for Scott encoded naturals $\mathbb{N} = \forall r. r \to (\mathbb{N} \to r) \to r$:

pred n = n 0 (\pn -> pn)

However, for the Church encoded naturals:

$\mathbb{N} = \forall r. r \to (r \to r) \to r$

writing the predecessor function is a challenging exercise (and the resulting function is expensive).


What exactly is the semantic difference between category and set? In this question, I asked what the difference is between set and type. These answers have been really clarifying (e.g. @AndrejBauer), so in my thirst for knowledge, I submit to the temptation of asking the same about categories:

Every time I read about category theory (which admittedly is rather informal), I can't really understand how it differs from set theory, concretely.

So in the most concrete way possible, what exactly does it imply about $x$ to say that it is in the category $C$, compared to saying that $x\in S$? (e.g. what is the difference between saying $x$ is a group, versus saying that $x$ is in the Category $\mathrm {Grp} $?).

(You may pick any category and set that makes the comparison most clarifying).

In brief, set theory is about membership while category theory is about structure-preserving transformations.

Set theory is only about membership (i.e. being an element) and what can be expressed in terms of that (e.g. being a subset). It does not concern itself with any other properties of elements or sets.

Category theory is a way to talk about how mathematical structures of a given type1 can be transformed into one another2 by functions that preserve some aspect of their structure; it provides a uniform language for speaking of a great range of types1 of mathematical structure (groups, automata, vector spaces, sets, topological spaces, … and even categories!) and the mappings within those types1. Although it formalises the properties of mappings between structures (really: between the sets on which the structure is imposed), it only deals with abstract properties of maps and structures, calling them morphisms (or arrows) and objects; the elements of such structured sets are not the concern of category theory, and nor are the structures on those sets. You ask “what is it a theory of”; it is a theory of structure-preserving mappings of mathematical objects of an arbitrary type1.

The theory of Abstract categories3, however, as just stated, totally ignores the sets, operations, relations and axioms specifying the structure of the objects in question, and just provides a language in which to talk about how mappings that do preserve some such structure behave: without knowing what structure is preserved, we know that the combination of two such maps also preserves structure. For that reason, the axioms of category theory require that there be an associative composition law on morphisms and, similarly, that there be an identity morphism from each object to itself. But it does not assume that morphisms actually are functions between sets, just that they behave like them.

  To be worked out: Concrete categories model the idea of adding structure to the objects of a ‘base category’; when this is $\mathsf{Set}$ we can have the situation where we add structure like a group operation to a set. In this case one may have more to say about how structure is added in terms of the specific base category.

As for the implications of your formulations, saying that “$G$ is a group”, that “$G$ is an element of the set of groups” (actually a proper class) or that “$G$ is (an object) in $\mathsf{Grp}$” (or a “$\mathsf{Grp}$-object”) mean the same thing logically, but talking about the category suggests you are interested in group homomorphisms (the morphisms in $\mathsf{Grp}$) and perhaps in what they have in common with other morphisms. On the other hand, saying $G$ is a group might suggest you are interested in the structure of the group (its multiplication operation) itself or perhaps in how the group acts on some other mathematical object. You would be unlikely to talk about $G$ belonging to the set of groups, though you could easily write $ G ∈ S $ for some particular set $ S $ of groups you are interested in.

See also

https://math.stackexchange.com/questions/tagged/category-theory?sort=votes

In particular https://math.stackexchange.com/questions/272875/concrete-category-and-abstract-category#1774821

Abstract and Concrete Categories: The Joy of Cats by Adámek, Herrlich and Strecker
https://en.wikipedia.org/wiki/Category_theory

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

1 Here and passim I do not refer to type in the sense of type theory, but rather a set of properties required of the mathematical objects/structures, i.e. a set of axioms they satisfy. Normally these describe the behaviour of some operations or relations on elements of the sets considered to carry the structure, though in the case of sets themselves ($\mathsf{Set}$) there is no structure beyond the sets themselves. In any case, as said above, category theory ignores the details of this structure.

2 I should perhaps say into all or part of one another: one allows the homomorphism from $ \mathbb Z $ (integers) into $ \mathbb Q $ (rationals) given by $ n \mapsto \frac n 2 $ .

3 Without qualification, ‘category’ normally means ‘abstract category’, introduced, as far as I can see, in 1945 and developed in the 1960’s while Concrete categories seem to appear in the 1970’s.


Asymptotic bounds on geometric sums So I'm doing exercises from Dasgupta's Algorithms. The exercise i'm having trouble with is:

Show that, if $c$ is a positive real number, then $g(n) = 1 + c + c^2 +...+c^n$  is:

$\Theta(1)$ if $c<1$

$\Theta(n)$ if $c=1$

$\Theta(c^n)$ if $c>1$

(I dont know if this is a hint but it is included in the text:
"The moral: in big-$\Theta$ terms, the sum of a geometric series is simply the first term if the series is strictly decreasing, the last term if the series is strictly indreasing or the number of terms if the series in unchanging")
The only one that makes sense for me is 2) where $1+1^2+..+1^n$ is the same as $n+1$, and removing the 1 gives $O(n)$. I dont know if my reasoning makes sense, but thats all i've got. I have no idea where to start or how to think on the other two. Any suggestions?

Hints:

In the first case, use the inequalities
$$
1 \leq \sum_{i=0}^n c^i = \frac{1-c^{n+1}}{1-c} \leq \frac{1}{1-c}.
$$
In the second case, use the inequalities
$$
c^n \leq \sum_{i=0}^n c^i = \frac{c^{n+1}-1}{c-1} \leq \frac{c}{c-1} c^n.
$$


What are functions called that yield the same result when applied to one of their result values Suppose one of the following holds for all x, or all y, or all z:

f(f(x)) = f(x)
f(f(y)) = f(y)
f(f(f(z))) = f(f(z)) = f(z)

... how do you call such a function?

A function satisfying that property is called idempotent.


rationale behind multi-layer networks I recently read that a feed forward neural network with a single hidden layer can represent any continuous function to great precision (ref.).
Then how can we justify adding more that one hidden layer to our network ?

The rationale is that the number of neurones you need to use for approximating any given contiguous function decreases as you add subsequent layers.
See Colah's Deep Learning, NLP, and Representations for a more in-depth explanation.


Reduce Min-Cut to 0/1 Integer Program Given an undirected, weighted graph $G=(V,E)$ and two nodes $s,t \in V$ and weight function $w: E \rightarrow \mathbb{N}$. The weight of a (s,t)-cut $ (U, U^C)$ is given by:

$$ w(U,U^C) := \sum_{\{i,j\}\in V :i\in U \land j\in U^C} w(\{i,j\}) $$

Reduce $$ MinCUT:= \{<G,c,s,t,k>\mid \text{There is a (s,t)-cut with weight} \leq k\} $$ to $$ BinaryProgram:= \{<A,b> \mid \text{There is
 a vector } y\in\{0,1\}^* \text{ such that } Ay \leq b \} $$

I know i have to find a matrix $A$ and a vector $b$ which implement the following constraints:

The weight of the edges which cross the sets of the cut must be $\leq k$
Node $s$ must be in set $U$ and node $t$ must be in set $U^C$
Every node must either be in $U$ or $U^C$

Can somebody give me a hint how implement these constraints into a matrix ?

Hint: Let's try to encode the constraints using two types of variables: $a_v$ for each vertex $v$, and $b_{uv}$ for each edge $u,v$. The variable $a_v$ encodes which part of the cut vertex $v$ belongs to. The variables $b_{uv}$ equals 1 if the edge $(u,v)$ is cut.

We want to enforce the following constraints:

$a_s = 0$ and $a_t = 1$.
$b_{uv} = 1$ if $a_u = 1$ and $a_v = 0$ or if $a_u = 0$ and $a_v = 1$.
$\sum_{uv \in E} w(u,v) b_{uv} \leq k$.

Try to encode all these constraints as inequality constraints.