Decision problem and algorithm I was reading about decision problem. I understand that decision problem tell yes/no answer for an input. The decision is based on a decision procedure also called an algorithm.

The wikipedia says that

  It is traditional to define the decision problem equivalently as: the set of inputs for which the problem returns yes.

  These inputs can be natural numbers, but may also be values of some other kind, such as strings over the binary alphabet $\{0,1\}$ or over some other finite set of symbols. The subset of strings for which the problem returns "yes" is a formal language, and often decision problems are defined in this way as formal languages.

Whether I can take it like algorithm written in a programming language defines the set of all possibilities and gives the output based on the input?

So in computability theory, the problem should be encoded to some form? Is this same thing as the input tape and configuration of a Turing machine (set of 0's and 1's )?

Traditionally, in computability theory all problems are encoded in terms of numbers, or sometimes strings of bits $0$ and $1$. This is a very "low level" kind of thing, it is like programming directly in machine code. The reason for doing this is mostly historic. Gödel originally encode first-order logic in terms of numbers to prove his incompleteness theorems. Similarly, if one approaches computability through recursive functions, it is natural to encode everything with numbers. And mathematicians just like numbers anyway.

A computer scientist would recognize the benefits of using a more advanced programming language that supports datatypes. Programmers know that programming in machine code obscures a lot of ideas and makes everything technically difficult. Mathematicians know this too, but since they do not actually write code, just think about writing code, they do not appreciate this point of view sufficiently to switch from their traditional ways.

So, to answer your question, here is a modern way of defining decision problems. Pick your favorite general-purpose programming language. Consider a datatype $D$ (can be numbers, lists, heaps, trees, whatever) and decompose the values into two disjoint sets $D_0$ and $D_1$, so that $D_0 \cap D_1 = \emptyset$ and $D_0 \cup D_1 = D$. Observe that $D_1$ uniquely determines $D_0$ and vice versa, because $D_0 = D \setminus D_1$. So we only have to specify $D_1$.

Now, a decision problem $(D_0, D_1)$ is said to be decidable if there is a program $p : D \to \mathtt{bool}$ such that:

$p$ is total, which means that $p(d)$ halts for every $d \in D$,
if $d \in D_0$ then $p(d) = \mathtt{false}$,
if $d \in D_1$ then $p(d) = \mathtt{true}$.

All that stuff about encodings and finite words over an alphabet etc. is not necessary. It is only useful if you want to prove general theorems about arbitrary decision problems. But if you want to think about a specific decision problem, it is better to do it directly in your favorite programming language.


Question regarding $O(n^2)$ efficiency I'm going through a video of EDX course which talks about Big O notation. At the end of the video they have some questions but the $O(n^2)$ answer is confusing me. It feels like a mistake, but I just want to make sure.
The question is :

Imagine that we have a data set of 10 items. We run an algorithm on that data set, and it performs 10 operations.
Now imagine that we doubled the size of the data set to 20 items. Approximately how many operations might now be required if the algorithm is of...

Linear order? 20

Constant Order? 10

Quadratic Order? 40

I don't understand why the answer if 40 if it's quadratic.
At first I thought it would be 400, because n2 is 400. But the drop-down answer menu doesn't have 400. The highest it has is 100.
So I thought it might be 100, because if 10 items take 100 operations, then increasing by 10, would increase by 100. However 100 seems to be wrong as well.
So why is the answer 40?
The course in question is here:
https://www.edx.org/course/introduction-computing-using-python-gtx-cs1301x
Chapter 5.2

Say the time spent is some constant factor $c$ times $n^2$. Then we have:

$$c \cdot 10^2 = 10$$
$$c = 0.1$$

Thus then $c\cdot 20^2 = 40$.


Is {ww^r ww^r} a context-free language? Is the language $L = \{w w^r w w^r \mid w \in \Sigma^*\}$ context-free? ($w^r$ is the reversal of $w$.)

I heard that by using the pumping lemma, we can only prove that a language is not context-free, but can't prove that a language is context-free. I tried the pumping lemma and we can produce the language by repeating $v$ and $x$ by taking first $ww^r$ as $v$ and the second $ww^r$ as $x$ which again belongs to the same language. However I'm not able to build any grammar or build a PDA with one stack. I know that may if someone tries harder than me they may be able to construct it, but I'm thinking this may not be a context-free language. Does anyone have any idea about this language?

It's not context free for the same reason that $L' = \{w w \mid w \in \Sigma^*\}$ is not context free, and the proof below is a simple adaption of the standard proof for the language $L'$, using the pumping lemma:
Choose the string $0^p1^p1^p0^p0^p1^p1^p0^p$, (which is $\omega \omega^r \omega \omega^r$ where $\omega = 0^p 1^p$). [Note 1] Now any $vwx$ whose length is no greater than $p$ is either entirely within the first half of the string, entirely within the second half of the string, or entirely within the central span of $0^{2p}$. Repeating $v$ and $x$ 0 times -- that is, changing $vwx$ to $w$ -- must make the first half of the string different from the second half, either because only one of the halves is altered, or because changing the suffix of one half and the prefix of the other half renders the two halves distinct. So the result is not in $L$.
Since for any $p$, we can find a string which cannot be pumped, we can conclude that there is no pumping length $p$ for the language. That contradicts the pumping lemma, which states that every context-free language has a pumping length. So the language is not context-free.

You can't “take the first $ww^r$ as $v$” because of the restriction that the length of $vwx$ is no greater than the pumping length $p$. So, whatever $p$ is (if it exists) there is some $ww^r$ which is longer, and for the corresponding string $ww^rww^r$ in $L$, $v$ cannot be $ww^r$.

Notes:

I could have chosen a shorter string, such as $\omega = 0^m1^n$ where $m>0, n>0, 4mn>=p$. But there are no prizes for parsimony here; the string I chose makes the proof less verbose.


Classifying infinite languages of encodings of halting Turing machines Given this question:

$L$ is an infinite language of encoded Turing machines who always halt.

$L$ might be decidable
$L$ might be in RE but not in R
both 1. and 2. are correct

I know the solution to this question is 3., but I seem to lack the understanding on how am I suppose to get to that solution. Could you explain how should I approach this kind of questions? Am I supposed to start drawing TMs?
Why is the answer is C? What's the indication of that?
It would help me a lot if you could explain to me your thought process when facing this kind of problem.

There are certainly examples for all "levels":

It is easy to give an infinite set of encodings that is decidable.

   Consider all programs of the form f(x) = x + i -- definitely an infinite and decidable set.

Classic examples (think Halting problem) are semi-decidable but not decidable.

   $L = \{ \langle M \rangle \mid f_M(\langle M \rangle) = 1\}$

Other classic examples (think complement of Halting problem) are not semi-decidable.

    $L = \{ \langle M \rangle \mid f_M(\langle M \rangle)\uparrow \}$


Is there a #$P$-complete counting problem such that every (valid) instance of its decision version is a Yes-instance? I want to know whether there is a decision problem, written EasyProblem, satisfying the follow property:

For every valid instance $x$, $x$ is a Yes-instance for EasyProblem (if we construct EasyProblem as a nature problem). Formally speaking, maybe we can define EasyProblem as a language $L \in \mathrm{DTIME}(n)$ or even $L \in \mathrm{DTIME}(1)$.

The counting version #EasyProblem is in #$P$-complete.

Really what I'm asking is: can we construct a very easy decision problem, but its counting version is too hard? Or can we construct a very hard counting poblem, but its decision version is too easy?

An example of a such problem in $\mathrm{DTIME}(n)$ is DNF satisfiability [1]. Its counting version is #P-complete [2], but its decision version can be solved by simply checking if there is a conjunction that is satisfiable.
For $\mathrm{DTIME}(1)$ I think the answer is that there are no such problems because we can iterate over all computation paths in $O(1)$ so counting is easy.
Note that in general, disallowing instances with answer 0 does not change the #P-completeness of any problem whose decision version is in P because we can check this case in polynomial time.
[1] https://en.m.wikipedia.org/wiki/Disjunctive_normal_form
[2] https://en.m.wikipedia.org/wiki/%E2%99%AFP-complete


What is the computational complexity of "real-life" regular expressions? Regular expressions in the sense as equivalent to regular (Chomsky type 3) languages know concatenation xy, alternation (x|y), and the Kleenee star x*.
"Real-life" regular expressions as used in programming usually have a lot more operations available; amongst others, quantification x{n}, negation [^x], positive and negative lookahead x(?=y), or back-reference \n.
There is a famous post on SO stating that regular expressions can not be used to parse HTML for the reason that HTML is not a regular language.
My question is: Is this accurate? Do "real-life" regular expressions, say the selection defined in the Java docs, really have the same expressive power as regular expressions as understood in formal language theory; or do the additional constructs, although possibly not strong enough to capture HTML and the like, put common regular expressions further up on the Chomsky scale than just Type 3 languages?
I would imagine the proof of the computational equality of the two would amount to showing that each operation available for the common regexp is just syntactic sugar and can be expressed by means of the 3 basic operations (concatenation, alternation, Kleene start) alone; but I am finding it hard to see how one would e.g. simulate back-reference with classic regexes alone.

The following extended regular expression matches the language $\{ ww : w \in \Sigma^* \}$:
$$
\texttt{^\\(.*\\)\\1\\\$}
$$
This language is neither regular nor context-free.
Matching using extended regular expressions is NP-complete; see for example this paper, which discusses efficient algorithms in some special cases.


Find witnesses (or not) I have just started learning Analysis of Algorithms and I came across these set of questions:

Find witnesses c and m such that rn+1 = O(rn) for r>1
Show that there are no witnesses for n2 = O(n)
From 2, deduce no witnesses for 22n = O(2n)

So, I have tackled some as:

rn+1 ≤ rn+1
rn+1 ≤ r.rn
rn+1 ≤ (r+1).rn
Therefore, c = r + 1; m = 1

n2 ≤ n2
No value for c satisfies the above inequality, therefore no witnesses (??)

22n ≤ 22n
No value for c satisfies the above inequality, therefore no witnesses (??)

I am not sure how to go about the last 2.
Can anyone please tell me whether what I have done is correct?

Thanks.

Part 1 looks OK.

For part 2, to show no witnesses exist, you have to proceed by contradiction. Assume witnesses $c,m$ exist, so we have $n^2 \leq cn$ for all $n\geq m$. Now, to reach a contradiction, find at least one value of $n \geq m$ for which $n^2 > cn$. The value for $n$ can be defined in terms of $c,m$. It shouldn't be too hard to find one.

For part 3, the text suggests to use 2. That is, to prove that if we had (by contradiction) witnesses for 3, we could derive from them some witnesses for 2.

(Honestly, to me this way sounds harder than simply tackling 3 on its own, without exploiting 2. Maybe you were introduced to some theorem which can apply here to shorten the exercise? I have no idea.)


Finding the best poker hand in a connected grid structure where order matters I am trying to find the best poker hand in a connected grid, where order matters. An illustration is the best way of explaining the situation.

This grid has 12 random cards, in random positions. Each card is connected to the vertically, horizontally and diagonally adjacent cards.

The hands are standard poker hands but no extra cards are allowed – only the cards which constitute the hand. So, a pair is only two cards connected, four of a kind is just four cards connected, etc.

The best hand for this grid highlighted:

Order matters, so a straight must be in the correct order (e.g. 10, J, Q, K, A is valid but 10, A, J, Q K is not). There is no straight in this particular grid, the 10s are not connected to the Jack directly.

I am looking for an algorithm that finds the best hand for a random grid. The grid isn’t ever going to be much larger than this grid of 12.

I am also looking for an algorithm that finds out if there are no moves at all – this would alert the player to this fact to save them searching for too long…

I recommend you use breadth-first search (BFS) through the state space.

Start by trying to find (partial) straights that are ascending.  For each possible starting position (there are 12 possibilities), use BFS to search for a path that starts at that position and makes an ascending straight (i.e., the numbers increment by one each time you move forward).  This will find you the longest ascending straight.

Next search for descending (partial) straights in the same way.  This will find you the longest descending straight.

You can also search for straight flushes in this way, too.

Next for x-of-a-kinds in the same way.  This will find you the longest sequence that are all of the same rank (e.g., two-of-a-kind, three-of-a-kind, four-of-a-kind, five-of-a-kind).

Next search for flushes in the same way.  This will find you the longest sequence that are all of the same suit.

You can look for two-pair and full-house separately, with a different method tailored to that problem.  Enumerate all pairs (i.e., all pairs of adjacent positions where the two cards have the same rank).  Now check whether any two of those pairs are adjacent; if so, you have found a two-pair.  Similarly, enumerate all three-of-a-kinds (i.e., paths of length 3 where the three cards have the same rank).  Now check whether any pair is adjacent to any three-of-a-kind; if so, you have found a full-house.

In this way you can find the best poker hand in the grid.  I expect that this will be very efficient.


Pac learnable when changing distribution if H is Pac learnable according to

  Definition 3.1 (PAC Learnability) A hypothesis class H is PAC learnable
  if there exist a function $m_H\colon(0,1)^2 \mapsto N$ and a learning algorithm with the
  following property: For every $\varepsilon, \delta \in (0,1)$, for every distribution $D$ over $X$, and
  for every labeling function $f \colon X \mapsto  \{0,1\}$,  if the realizability assumption holds
  with respect to $H,D,f$, then when running the learning algorithm on $m \geq m_H(\varepsilon, \delta)$ i.i.d. samples generated by $D$ and labeled by $f$, the algorithm returns
  a hypothesis $h$ such that, with probability of at least $1 - \delta$ (over the choice of the examples), $$L_{(D,f)}(h) \leq \varepsilon.$$

and the algorithm returns h* (for specific S of size
$m_H(\varepsilon, \delta$) and distribution D) , I can define a distribution D' that gives 0 for each x s.t. h*(x)=f(x) and that will give me $L_{D'}(h*)=1$.
I am trying to understand why this is ok (not a contradiction for H being PAC), so I have 2 questions on this:
$$$$
1. my guess is that since the algorithm does not depend on the distribution but does on S (that depends on it), we will probably get with the new distribution D' a different S that will return a different h that keeps us with $L_{(D',f)}(h) \leq \varepsilon.$ with probability $1 - \delta$. Is this the right explanation?
$$$$
2. After defining the new distribution D' is it right to say that (D',f,H) still hold the realizability assumption? I don't see why not but want to be sure.

  definition 2.1 (The Realizability Assumption) There exists $h* \in H$ s.t.
  $L_{(D,f)}(h*) = 0.$. Note that this assumption implies that with probability 1 over
  random samples, S, where the instances of S are sampled according to D and
  are labeled by f, we have $L_S(h*) = 0$.

Thank you

I think the definitions in that book are unclear. If you note, the realisability assumption is not stated as an assumption on anything, nor as a standalone definition, so that already is a bit confusing. I have struggled to find one anywhere that is clear actually.

It appears to me that The Realisability Assumption is also dependent on the distribution  $D$ and the labelling function $f$. That is the trio ($H, D, f$) can be realisable. $H$ in and of itself cannot be realisable.

It took me some sleuthing to come to this conclusion, and I hope it is the right one. I think you are nearly on the right lines of thinking. Here is my thinking:

As you say, if we choose a distribution that causes problems then perhaps we can prove that $L(h) = Err(h) > 0$. If you assume $H$ is finite, and $f$ is not in $H$, then we can find problematic points $x$s and put positive probabilities on them. Then for every $h$ in $H$, $L(h) > 0$; i.e. $H$ is not actually realisable with respect to any distribution.

We have made an assumption that $H$ is finite, but given that the book later on goes on demonstrate results with realisability, and finite $H$, I think we should assume that realisability and finite $H$ together are a valid consideration, and therefore, we cannot assume that realisability holds across any distribution over the domain set $X$. I think therefore we should assume that that is what they meant when defining realisability.

Similarly for the labelling function $f$. If $H$ and $D$ are realisable, independently of $f$, then in the case where $H$ is finite and contains only one hypothesis $h$, we can choose an $f$ that is different to h on the whole domain, which would result in $Err(h) = 1$.

So here's how I would state the Realisability Assumption:

  Definition (The Realisability Assumption) Given a learning problem with distribution $D$ over the domain set, and labelling function $f$, then a set of hypotheses, $H$, is Realisable if there exists $h* \in H$ s.t.
  $L_{(D,f)}(h*) = 0$.

Note that you do not need to know what $D$ and $f$ are to assume that $H$ is realisable with respect to them. We can just assume that $H$ is realisable with respect to them, whatever they may be.

So, assuming realisability in PAC Learnability also restricts $D$ and $f$ to be those which are realisable w.r.t. $H$.


How can can I find out if the two disks intersect in the plane? . Imagine two disks on the xy plane. Each disk is represented by
three numbers (the radius, the x coordinate of the center and the y coordinate of the center). All values
for this problem are real numbers. Your task is to determine if the two disks intersect.

I am not sure if I should answer such a question, but here we go:

Let the first disk be $D_1 = \langle R_1, (x_1, y_1)\rangle$ and the second disk be $D_2 = \langle R_2, (x_2, y_2)\rangle$, where $R_1$ and $R_2$ is the radius of the first and second disk respectively, as well as $(x_1, y_1)$ and $(x_2, y_2)$ is the center of the first and second disk respectively. Further, let $d$ be the distance of the two centers; that is, $$d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}.$$ Then, the two disks intersect if $$d \leq R_1 + R_2$$ and do not intersect otherwise.

Note that if $d = R_1 + R_2$, then the two disks have only one point in common.


Prove number of nodes in heap Consider a variation of the normal heap which we will call the x-heap

The x-heap of height $h$ has the following properties:

It will have $2^h$ nodes
A height of $0$ corresponds to the single root node
The format of the tree is a root with exactly one child, which in turn is the root of a complete binary tree

We define a collection of x-heaps to be sequence $X_0, X_1,\dots,X_k$ with the following properties:

$height(X_{i-1})\leq height(X_i)$, where $0\leq i \leq k$
There exist at least $i + 1$ (X-heaps) of $height \leq i$, where $0\leq i \leq k$
There exist at most $i + 2$ (X-heaps) of $height \leq i$, where $0\leq i \leq k$

We cannot have a collection with all of the same type of x-heap (can't have collection with all single nodes)

Prove that if $X_0,X_1,\dots,X_k$ is a collection, then the total number of nodes is between $2^k$ and $2^{k+1}$

I am not sure where to start here. I feel I must use the last two bullet points, but not sure how.

Moreover, the trees in a collection can have height $1, 3, 4, 8$ as an example. It is not limited to increasing by $1$.

Interesting proposition.

Moreover, the trees in a collection can have height 1,3,4,8 as an example. It is not limited to increasing by 1.

How could 1,3,4,8 be an example? If you set $i=0$ in "there exist at least $i + 1$ x-heaps of $height \leq i$, where $0\leq i \leq k$", you know there exist at least 1 X-heap of height less than or equal to 0. That means $X_0$ must be 0. In fact, the height will be increased by 0 or 1 every time.
Reformulation
Since an x-heap is completely determined by its height, let us introduce almost-natural sequences, which comes from a collection of x-heaps in the question.
An almost-natural sequence is a non-decreasing sequence of integers $0=h_0, h_1,\dots,h_k$, where $k\ge0$, such that, for all $0\le i\le h_k$,

at least $i + 1$ of them are not greater than $i$
at most $i + 2$ of them are not greater than $i$.

Characterization of almost-natural sequences. An almost-natural sequence must be one of the following.

$0, 1, \cdots, k-1, k$, i.e., the first $k+1$ natural numbers.
$0, 1, \cdots, m-1, m, m, m+1, \cdots, k-2, k-1$, i.e., the first $k$ natural numbers with one of them, $m$ repeated once, where $0\le m\le k-1$.

Corollary. $2^k\le\sum_{i=0}^k2^{h_k}\le2^{k+1}-1$ for an almost-natural sequence $h_0,h_1,\dots,h_k$.
Exercises
Here are a few related exercises.
Exercise 1. Prove the characterization of almost-natural sequences.
Here is a hint. Does a given almost-natural sequence contain a repeated number? If yes, prove that number appears exactly twice and no other number is repeated.
Exercise 2. Prove the corollary.
Exercise 3. Let a d-natural sequence be a non-decreasing sequence of $k+1$ integers $0=h_0, h_1,\dots,h_k$ such that at least $i+1$ and at most $i+1+d$ of them are not greater than $i$ for all $0\le i\le h_k$. Determine the lower bound and upper bound of $\sum_{i=0}^k{h_k}$ and $\sum_{i=0}^k2^{h_k}\,.$


How to Optimise the following algorithm? maximum good value of an element in an array I was recently stuck while doing a question, please suggest a way with a code/pseudo code to optimize the following algorithm for finding the maximum good value in an array where a good value of an array element $A_i$ is defined as the total no. of Valid indices $<$ such that $_$ is divisible by $_$. My approach is as follows,

    int maximum=-1;
    for(int i=n-1;i>=0;i--){
        int count=0;
        for(int j=0;j<i;j++){
            if(arr[j]%arr[i]==0)
            count++;
        }
        maximum=max(count,maximum);
     }
     print(maximum);

Depending on the input values the following strategy might work:
keep an array $C$ of $10^6$ elements where $C[i]$ will store the number of times number $i$ appears in the elements of the input array that have already been processed.

Initially $C$ is identically 0, then you consider the elements $A_i$ one at a time. When you are processing the $A_i$ you can compute the "good value" by taking the sum of all $C[k A_i]$ for $k=1,\dots,\lfloor 10^6 / A_i \rfloor$. Then, increment $C[A_i]$.

At the end of the process return the maximum sum.

A more refined strategy is that of handling separately small and large values of $A_i$. If $A_i \ge 1000$ then the above algorithm check at most $10^3$ entries in $C$.
If $A_i < 1000$ then you can find the number of its multiples by checking and keeping track of how many of the input elements seen so far are divisible by the numbers between $1$ and $1000$. This also requires $\approx 1000$ operations. So you'll be performing $\approx 2 \cdot 10^5 \cdot 10^3$ operations as opposed to $10^{10}$ of your algorithm.

An even better strategy is to keep an array $D$ where $D[n]=j$ means that  $j$ of the numbers seen so far have $n$ a divisor. Since the number of divisors grows slowly (as $O(\log n / \log \log n)$, and it is always at most $240$ for your values) this strategy will only increment a few values per input number (less than 14 on average, assuming an uniform input distribution. See here for a plot of the number of divisors of the first $10^5$ integers).
The leaves you with a number of operations of the order of $10^6$ to $10^7$.

The problem is now that of enumerating, for each number $n$, its divisors efficiently. But you can just do this as a preprocessing step by multiplying each $i=1,\dots,10^6$ by consecutive integers $k$ until it exceeds $10^6$. For each such $k$ add  $i$ to the list of divisors of $k \cdot i$. This could even be done once-for-all and hardcoded in your algorithm.


Predicitve Parser LL(1) condition Lets say we use the predictive parser LL(1). Why is it necessary that
$FIRST(\alpha) \cap FIRST(\beta) = \emptyset$,
for all $\alpha, \beta$ right side of alternative productions i.e., productions associated to the same non-terminal. Why is this condition necessary?

Here's an intuitive explanation:
It follows essentially from the nature of LL(1) parsers: LL(1) parsers build a LL(1) parsing table. The rows of the table are nonterminals, and the columns are terminals. We can think about LL(1) parsing as doing LL(1) table lookups upon encountering each symbol in the input: we look at the entry determined by the current nonterminal and the input terminal, and apply a corresponding production rule. Thus, the LL(1) table cannot contain multiple production rules at each entry, otherwise, the parser cannot decide which rule to apply.
If the right hand side of a production $\alpha$, $\beta$ have intersecting FIRST sets, then we'd have multiple rules at a single entry in the LL(1) table (i.e. duplicate/conflicting entries) --- having nontrivial intersection of FIRST sets essentially prevents us from constructing the LL(1) parsing table.
If you're still unclear about why this condition is necessary, I suggest you construct an example with intersecting FIRST sets on the right hand side of a production, and then try to manually construct an LL(1) parsing table or use one of the online visualization tools; you'll immediately find a conflict.


Prove NP-completeness for union of NP-complete language and language in P Given disjoint languages $X$ and $Y$, where $X$ is NP-complete and $Y\in P$ , how do I prove that $X\cup Y$ is NP-complete?

My idea is to prove that $(X\cup Y)\in NP$ and then prove that $X\cup Y$ is NP-hard:

I can prove $(X\cup Y)\in NP$ by saying that since both are in NP, they each have polytime verifiers. Thus we can have a polytime verifier that on any input will use these verifiers and accept if any accept, reject otherwise.

I am stuck on the part of proving NP-hardness. The idea of arbitrary languages is throwing me off; I am trying to reduce a NP-complete problem (SAT for example) to $X\cup Y$ and using the fact that $X$ has some method to reduce to it already but I am lost as for what to do with $Y$. I am thinking that given an input for SAT, I need to somehow change the input so that I can relate acceptance in $X\cup Y$ to acceptance in SAT; same for rejection.

Any guidance would be appreciated; thanks!

If for any two disjoint languages $X,Y$, we have:

$\textbf{*} \hspace{1mm} X \text{ is NP-complete} \land Y\in P \Rightarrow X\cup Y\text{ is NP complete}$

then $P\neq NP$.

Let $L$ be some NP-complete language. $L\cup\overline{L}=\Sigma^*$ is not NP-complete, thus, using (*) we obtain $\overline{L}\notin P$, but $L\in P\iff \overline{L}\in P$.

In fact your statement is equivalent to $P\neq NP$. You can prove the opposite direction by using the fact that if $P\neq NP$ and $L$ is NP-complete, then $\overline{L}$ is not in $P$. In that case, you can reduce $X$ to $X\cup Y$ by checking if the input is in $Y$, and output some constant word outside of $X\cup Y$ if it is. This can be done since we know now that $Y\subsetneq \overline{X}$.


Why is a superscalar processor SIMD? From http://en.wikipedia.org/wiki/Superscalar

  In Flynn's taxonomy, a single-core superscalar processor is classified as an SIMD processor (Single Instructions, Multiple
  Data),

Flynn's taxonomy is based on number of instruction streams and
number of data streams.

A superscalar processor can run more than one instructions at a
time, so why isn't it MIMD?

If there is a valid reason for a superscalar processor to be SI,
then why isn't there a similar reason which makes it single-data (i.e.
SISD)?
Instruction pipeline also runs more than one instruction at one
time. Is it SISD or SIMD?
Does "SI $\equiv$ only one CPU core"? Or only one implies the other?

Does "MI $\equiv$ more than one CPU cores"? Or only one implies the other?

Thanks.

First, Wikipedia is wrong in classifying superscalar processors as SIMD (except as many modern superscalars also support short vector instructions). A superscalar has one instruction stream, i.e., there is conceptually only one current instruction address from which instructions are fetched. However, it also has only one data stream, i.e., it generally does not apply the same instruction to multiple data as a vector processor would. (from "Some Computer Organizations and Their Effectiveness" (Michael J. Flynn, 1972): "The single-instruction stream-multiple-data stream (SIMD), which includes most array processes, including Solomon [2] (Illiac IV).")

Pipelining does not increase the number of instruction streams being processed in parallel; the single stream simply flows through a longer channel as it were.

A single processing core can have multiple instruction streams by using multithreading. (Multithreading cores often present this as virtual cores, i.e., to software each thread appears to have a full core, as a convenience for operating systems, allowing any multiprocessor-capable OS to trivially support multithreading. However, this is not a necessary feature; the MIPS MultiThreading Application Specific Extension, e.g., differentiates between a Virtual Processing Element and a Thread Context.)

More interesting cases would included decoupled access/execute architectures, GPUs which provide some instruction stream divergence, and a traditional ISA that internally (microarchitecturally) uses speculative multithreading.

Decoupled access/execute architectures have two partially independent instruction streams, one performing memory accesses and address calculations, the other performing computation, e.g., see James E. Smith, "Decoupled Access/Execute Computer Architectures" (PDF, so they are not neatly classified as having a single instruction stream but they do not have the extent of independent instruction flow associated with Flynn's Multiple Instruction classifications.

Similarly, some GPUs support some control diverge (different instruction streams applied to different data), which is conceptually similar to applying eager execution (where multiple conditional paths are executed in parallel and only the results of the correct path are committed) to multiple data (where at least one of the data elements unconditionally does follow that execution path). This type of architecture is sometimes called Single Program Multiple Thread or Single Instruction stream Multiple Thread. (Note that GPUs also commonly support more traditional MIMD multithreading.)

Hardware speculative multithreading presents the interface of a single instruction stream, but such uses a microarchitecture that supports multiple partially independent instruction streams. For example, loops might have iterations distributed across multiple threads and function calls might spawn a separate thread while processing continues at the return point (possibly using a predicted return value). Like GPUs and decoupled access/execute, this provides limited independence among instruction streams, but even MIMD programs often have limited independence, synchronizing instruction streams at join points. However, unlike those architectures, hardware speculative multithreading provides a SISD interface to software, so from the programmer's perspective it is SISD while from the hardware perspective it is more like MIMD.


Benford's law is not working? So I recently came across Benford's law and immediately tried to code it out but the answer I got was rather confusing. I've been thinking about it for about an hour now and still can't get it,  I think my code is correct I'm pretty sure it is but the result is just not the one others get. Here's the code:
float[] a=new float[10000],flag=new float[10];

for(int i=0;i<10000;i++)
  {
    a[i]=floor(random(0,99999));
      if(a[i]>10000)
         a[i]=floor(a[i]/10000);
      if(a[i]>1000)
         a[i]=floor(a[i]/1000);
      if(a[i]>100)
         a[i]=floor(a[i]/100);
      if(a[i]>10)
         a[i]=floor(a[i]/10);

      for(int k=1;k<10;k++)
       {
          if(a[i]==k)
            flag[k]++;
       }

  }

Though I get roughly the same flag[k] (around 1100) but according to Benford's law that should not be the case. Can someone help me tell how my code is wrong?

That's because for the numbers from 10,000 to 99,999 the first digit is equally likely, same for numbers from 1,000 to 9,999 etc.
Benford's law depends on random numbers whose logarithm has a linear distribution over a not too small range. Take random numbers x from 0 to 999,999, then calculate 10^(x/200000) and you'll find that Benford's law will hold.
But measure the height of adult people in feet, and 95% start with 5 or 6, a few percent start with 4, and very few with 7 or 3. It's not a law that applies to every set of numbers. (Measure people in meters, and 98% start with 1, a few with 2, and very few start with a 9 or even 8. )


Finding errors in weighted graphs I have a weighted graph where each edge is a 1d vector eg if weight going from A to B is 1 then from B to A it is -1. In the graph each cycle should add to zero though sometimes the weights have errors  and in that case a cycle will not add to zero.

So for example if the weight from A to B is 1 and B to C is 1 then for the cycle to sum to zero C to A must be -2 and there is an error if it is anything else. Please note that in general the cycles can involve an arbitrary amount of nodes.

What is the best algorithm for detecting these errors? IE what is the best algorithm for finding all weights that have errors and so are causing the cycles to add to a non zero value?

One approach is to compute the distance $d(u,v)$ between each pair $u,v$ of vertices using an all-pairs shortest paths algorithm, such as Floyd-Warshall.  Then, if $d(v,v) < 0$, you know that there exists a cycle through $v$ that doesn't add to zero.  You can explicitly find one such cycle by augmenting the shortest-paths algorithm with predecessor links to keep track of an example shortest path from $v$ to $v$.  Then you know that at least one of the edges along that cycle has an error.

Unfortunately there doesn't appear to be any way to uniquely determine which edges are in error.  For instance, consider a graph with edge $a \to b$ of weight $1.01$ and edge $b \to c$ of weight $-1.48$ and edge $c \to a$ of weight $0.50$; you know that at least one of those edges has an error, but there's no way to know which one; it could even be all of them that have an error.


Expected number of maximal cliques in $G(n,p)$ The $G(n,p)$ random graph model creates graphs with $n$ vertices and each possible edge exists independently with probability $p\in (0,1)$.

Much is known about the (expected) size of a largest clique in these graphs, and it has been shown that the expected number of maximal cliques of size $d$ is

$${n\choose d} p^{d \choose 2} (1-p^d)^{n-d}.$$

To find the expected number of maximal cliques,  just sum over all values of $d$ to get

$$\mu (G(n,p)) := \sum_{d=1}^n {n\choose d} p^{d \choose 2} (1-p^d)^{n-d}.$$

I'm interested in the asymptotic growth of $\mu (G(n,p))$ as a function $n$. For example, if $p$ is fixed, does $\mu$ grow polynomially in $n$?

A quasi-polynomial bound is not hard to show. Since the expected maximum clique size is roughly $\omega(G(n,p))\approx\frac{2 \log n}{\log(1/p)}$, the number of cliques (not necessarily maximal) is $O( {n \choose \omega(G(n,p))+1}) = O(n^{\omega(G(n,p))+1})=O(n^{\frac{2 \log n}{\log(1/p)}+1})$.

Since $\mu$ is the sum of $n$ terms, we can estimate it up to a factor of $n$ by the maximal term:
$$ \max_{d=1}^n \binom{n}{d} p^{\binom{d}{2}} (1-p^d)^{n-d} \leq \sum_{d=1}^n \binom{n}{d} p^{\binom{d}{2}} (1-p^d)^{n-d} \leq n\max_{d=1}^n \binom{n}{d} p^{\binom{d}{2}} (1-p^d)^{n-d}. $$
In order to find out which term is the largest, we can use the estimate
$$ \log_2 \binom{n}{d} p^{\binom{d}{2}} (1-p^d)^{n-d} \approx nh(d/n) + \binom{d}{2} \log_2 p - (n-d)p^d, $$
which is true up to polynomial factors for $d = \omega(1)$. We can estimate the magnitude of the largest term by differentiating this quantity with respect to $d$. If you follow this path, you should obtain an estimate for $\mu$ which is tight up to polynomial factors in $n$.


Do different variants of Mergesort have different runtime? One of my courses introduced the following question:

Given the recurrence relation for mergesort:
$T(n) = 2T(n/2) + n$
How would the following parameter passing strategies influence the relation and running time of the algorithm:

A pointer to the array is passed to the sorting function,

The entire array is copied to a separate location before applying the sorting function,

A subsection of the array is copied to a separate location before applying the sorting function on that subsection.

For 1., since this is how mergesort is used most of the time, we can solve it easily using the master theorem.
$f(n) = \Theta(n^{\log_b a}) = \Theta(n) \implies T(n) = \Theta(n \log n)$
For 2. however, I am a bit baffled. Although we do an additional work of $O(n)$, we are only doing so once at the beginning of the sort. Hence, doing one additional instance of $O(n)$ work should not influence the order of the running time (because it already is of a larger order). Hence, for both 2. and 3. the running time would remain at $T(n) = \Theta(n \log n)$.
Is this reasoning valid? Something tells me that the $O(n)$ copying should have more of an impact, but I can't seem to give myself a good enough reason that it should be responsible to slow it down enough so that it would worse (i.e. $O(n^2)$).
Any thoughts or hints would be quite appreciated!

Note first that we are talking about an algorithmic idea here; in order to apply a meaningful analysis, we would need at least pseudocode for the three variants.

Note furthermore that the given recurrence is most likely only valid in the limit. It is also not clear what the complexity measure is. Comparisons? In that case, it is clear that none of the adaptions change the measure at all. Basic operations? That would make more sense.

I agree with your reasoning; this seems to be the basic variant. Note again, however, that you'd have to look in the actual algorithm for its analysis. In particular, applying Mergesort in-place is uncommon.
Copying the entire array once adds a linear term globally, so the recurrence does not change. If you are only after $\Theta$-behaviour, ignore it (since the actual algorithm dominates).
Now this adds linear overhead to every call of the routine, changing the recurrence from $\ldots + n$ to something like $\ldots + 2n$. Of course, this results only in a different constant so the result is again not influenced (see Master Theorem).


How many permutations for generating a specific binary search tree? The keys 2, 4, 6, 7, and 8 have been inserted, one by one, in some unknown order, into an initially empty BST.  The result is this BST:

There are 120 different permutations of the five keys, but not all of these would lead to this particular BST being built.  How many of the permutations will generate this particular BST?

In a BST we can't say anything regarding the order of elements that are on separate sides of a node (e.g. 4 and 8, because they are on separate sides of node 6), however, we know that if a node is a parent of another node, it must have been inserted before it.

So 6 is always going to be the first element. Then either 4 or 7 can come (two choices). Then if we look at the remaining structure, 4/2 and 7/8 have exactly the same structure, so we can analyze just one.

Without loss of generality, assume we picked 4. Afterwards we can choose either 2 or 7 (two choices).

If we chose 2, no choice is left. However if we chose 7 either 2 or 8 can come next (two choices). Then we're left with no choice.

So the total number of permutations is $2(1 + 2) = 6$. The permutations are:

64278
64728
64782
67842
67428
67482


Assignment Problem - multiple tasks, but only one chosen based on their preference (cost) I've looked at Hungarian algorithm and Knapsack problems and neither quite hit the nail on the head. I've been trying to best rephrase my question while searching for answers and haven't got anywhere.

I have agents j and tasks i. Each agent can have between 1 and 4 task preferences (each with the cost 0-3), but must have only one task assigned by the end.

Each task also has a maximum number of agents that can be assigned to it (depending on the task).

Is there an algorithm out there that will minimise the overall cost, while maximising the amount of agents assigned to each task?

I hope that's clear, never really done this sort of thing before!

This can be reduced to minimum-cost flow, for which there are polynomial-time  algorithms.

Build a bipartite graph, with one vertex on the left for each agent, and one vertex on  the right for  each instance of a task.  Tasks are duplicated according to the maximum number of agents they can be assigned to.  For example, if task $i$ can be assigned up to 5 agents, then there will be 5 vertices on the right corresponding to task $i$.  If agent $i$ has a cost of $c_{i,j}$ for task $j$, add an edge of cost $c_{i,j}$ and capacity 1 from the vertex for agent $i$ to each vertex for task $j$.

Also, add a source vertex and an edge of cost 0 and capacity 1  from the source to each left vertex; and add a sink vertex and an edge of cost 0 and capacity 1 from each right vertex to the sink.  Now, find the minimum-cost flow that sends at least $n$ units of flow from the source to the sink, where $n$ is the number of agents.  That will be the solution to your problem.

There are many algorithms for solving minimum-cost flow problems, and even some off-the-shelf tools.  See Wikipedia for some references that will get you started to learn more.


Variation to edit distance depending on position still a metric? The edit distance between two strings $d(w_1, w_2)$  sums up the cost of edit operations that transform one string into the other. If done right, the edit distance is a metric.

In particular, the cost of an edit operation may depend on the character inserted or deleted, meaning we have costs $w_\text{insert}(a)$ and $w_\text{delete}(a)$ for all characters $a$.

Question: If the cost also depends on the position in the input string where it is applied, will the result still be a metric?

As an example, consider a spell checker that assumes mistakes in the first character of a word are rather seldom as compared to other positions, so when searching for corrected words, a change in the first position would have high cost.

Here is why the usual edit distance is a metric:

$d(w,w) = 0$ since no operations need to be performed to get from $w$ to $w$.
$d(x,y) = d(y,x)$ since given a sequence of operations for transforming $x$ to $y$, we can perform it in reverse to transform $y$ to $x$ at the same cost. This shows that $d(y,x) \leq d(x,y)$, and similarly $d(x,y) \leq d(y,x)$.
$d(x,y) \leq d(x,z) + d(z,y)$ since if $\alpha$ transforms $x$ to $z$ and $\beta$ transforms $z$ to $y$ then $\alpha\beta$ transforms $x$ to $y$, and moreover the cost of $\alpha\beta$ is the sum of the costs of $\alpha$ and $\beta$.

Now you're in a position to answer your question yourself.


Lower bound on competitive ratio of $m$-machine scheduling Given a sequence of positive reals $a_1, a_2, \dots, a_n$ and an integer $m$, for each $j$ assign $a_j$ to a machine $i$, $1< i < m$, so as to minimize the maximum, over $i$, of the sum of all reals assigned to machine $i$.

Theorem: There is no randomized $m$-machine scheduling algorithm with a competitive ratio less than $4/3$ for any $m \geq 2$.

The following is the Proof Sketch given in the paper:

  Consider the job sequences $m \times 1$ and $m \times 1, 2$. (Here $m \times 1$ denotes a sequence of $m$ 1’s.) If the algorithm schedules the $m$ 1‘s on $m$ different machines with probability $p$, the worst-case ratio between its cost and the optimal cost is at least $\max\{2 – p, 1 + p/2\} \sim 4/3$.

I have problem understanding the proof. I would really appreciate if anyone can explain the proof in details, especially how to arrive at the worst-case ratio of $\max\{2-p, 1+p/2\}$.

Consider first the sequence $m \times 1$. If the algorithm schedules all the 1's in different machines, then its competitive ratio is 1. Otherwise, its competitive ratio is at least 2 (since the maximum is at least 2 instead of the optimum 1). This case gives an average competitive ratio of at least $p \cdot 1 + (1-p) \cdot 2 = 2-p$.

Consider next the sequence $m \times 1, 2$. If the algorithm schedules all the 1's in different machines, then its competitive ratio is 3/2, since the maximum is 3 while the optimum is 2. If it doesn't schedule the 1's in different machines, we use the trivial bound on the competitive ratio. This case gives an average competitive ratio of at least $p \cdot (3/2) + (1-p) \cdot 1 = 1 + p/2$.

We conclude that the competitive ratio is at least $\max(2-p,1+p/2)$. If $p \leq 2/3$ then $2-p \geq 4/3$, whereas if $p \geq 2/3$ then $1+p/2 \geq 4/3$, and so whatever the value of $p$, we get that the competitive ratio must be at least $4/3$.


Can a non-deterministic machine merge its branches? Does an NDTM have the power to combine computational branches ie. can a result from branch A be used in the next step in the computation along branch B? Can branches use each others' results, diagrammatically 'merging'?

Example:

Branch i arrives at the number b after n steps, branch j arrives at the number c after 2n steps. After we have waited for both to arrive at their respective values, the computer, on the next step, multiplies those values 3*5 (effectively merging the different branches). Can it do this?

One view, explained by Tom here, is that nondeterministic branches work in parallel.

A more standard view, I think, is to view nondeterminism the way it is treated in physics, in logic, and in Dijkstra/Hoare style algorithm specification: at certain points, multiple continuations are possible, one of which will be taken. The 'multiple possible universes' do not exist in parallel, but they are alternative potential states of the world, alternative ways for the algorithm to continue, one of which will become reality.

So no, steps taken in one branch are not available in another branch. You either follow one branch or the other.


Do not understand a concept in analysis of open-address hashing I am reading the "Introduction to Algorithms" by Thomas Cormen et al. Particularly the theorem which says that given an open-address hash table with load factor α=n/m<1, the expected number of probes in an unsuccessful search is at most 1/(1−α), assuming uniform hashing.

In the proof they are saying -

$p_i$ = It is the probability of exactly i probes where we are finding all of the slots to be occupied. i is 0,1,2,…

$q_i$ = It is the probability of at least i probes where we are finding all of the slots to be occupied. i is 0,1,2,…

Then it says -

$$\sum_{i=0}^\infty i\,p_i\, = \sum_{i=1}^\infty q_i$$

How it is so?

For any $i$, $q_i = p_i + p_{i+1} + p_{i+2} + \dots$.  Now look at $\sum_{i\geq 1}q_i$ and how many times each $p_i$ occurs.  $p_1$ occurs only in $q_1$; $p_2$ occurs in $q_1$ and $q_2$; and, in general, $p_i$ occurs only in $q_1,\dots, q_i$.  In other words, each $p_i$ occurs $i$ times in the sum of the $q_i$s.


Is it decidable "Given a TM M, whether M ever writes a non blank symbol when started on the empty tape." I came across below problem in this pdf:

  Given a TM M, whether M ever writes a non blank symbol when started on the empty tape.

Solution given is as follows:

  Let the machine only writes blank symbol. Then its number of configurations in the com computation on w is q × 2, where q is the number of states of M; the factor 2 is for the choices re. the direction of heads movement; there is no factor for the written symbol because that is always blank. So the problem is decidable, decided by the following machine: input (M,w), run M on w for q × 2 steps; if it M ever writes a non blank symbol, stop with yes answer; if M never writes a non blank symbol, stop with no answer

Doubts:

Q1. How be sure all q x 2 configurations will happen while running q x 2 steps on w? Some configuration may get repeated in q x 2 steps.

Q2. Question says "when started on the empty tape", but the answer tried to simulate  TM on non empty string w. How does it makes sense?

Q1: A state can get repeated. The point is that if a state gets repeated and no non-empty symbol has even been written, then you known the that the Turing machine will never halt as it is necessarily stuck cycling through some of the states encountered so far. Since none of the states of the cycle caused the TM to write a non-blank symbol, the TM will never write a non-blank symbol.

After $2q$ steps, either a non-blank symbol has been written, and you can answer "yes", or all the written symbols were blank and (at least) one state must have been encountered two or more times, meaning that you can answer "no".

Q2: My guess is that $w$ is defined somewhere to be the empty string.
If the TM can be started with some arbitrary string $w$, then a variation of the above solution still works.
Suppose that the head of the TM starts at the beginning of $w$.
The number of states increases by a factor of at most $1+|w|$ in order to take into account all possible states of the tape (if only blank symbols are written, then the tape always contains one of the $1+|w|$ suffixes of $w$). If the head can start anywhere then this factor will be at most $1+|w|^2$.


How to prove $n^4 = \mathcal{O}(2^n)$? I'm new to asymptotic notations and right now I'm trying to prove that $n^4 = \mathcal{O}(2^n)$.
In my current solution (written below) I used L'Hôpital's rule repeatedly, proving that the limit of $n^4/2^n$ goes to zero. Is this correct?
Additionally I'm wondering whehter there is a simpler solution to this problem.
I tried induction but didn't get far. If you see an easier solution I would gladly appreciate any hints.

Thanks for any answers.

$ \lim_{n\to\infty} \frac{n^4}{2^n} = \lim_{n\to\infty} \frac{4*n^3}{2^n * ln(2)} = ..... = 0$

You mentioned trying induction, to no avail. However, induction does work. Let's prove by induction that for all $n \geq 6$, $$n^4 \leq \frac{81}{4} 2^n.$$
This is true for $n = 6$ (both sides are equal to 1296). Suppose that it holds for some $n \geq 6$. Then
$$
(n+1)^4 = \left(\frac{n+1}{n}\right)^4 n^4 = \left(1 + \frac{1}{n}\right)^4 n^4 \leq \left(1 + \frac{1}{6}\right)^4 n^4.
$$
You can calculate that $(7/6)^4 < 2$ (equivalently, $2401 = 7^4 < 2 \cdot 6^4 = 2592$). Therefore, using the induction hypothesis,
$$
(n+1)^4 < 2n^4 \leq 2 \frac{81}{4} 2^n = \frac{81}{4} 2^{n+1}.
$$
Thus the inequality holds for $n+1$ as well, completing the proof by induction.


Upper bound for size of minimal covers of a set Would appreciate any insight about the following regarding set covers:

Begin with a universe set $X = \{x_1,x_2,...,x_n\}$ and a set $S=\{s_1, s_2,...,s_p\}$ such that each $s_i \subseteq X$ and $\bigcup S = X$.    Consider the task of finding all inclusion-minimal covers of $X$.  (Covers are inclusion-minimal if the removal of any subset $s_i$ from the cover destroys its coverage property.)

Given the set of inclusion-minimal covers $C=\{c_1, c_2, ... c_m\}$, what is an upper bound for $\max|c_i|$, that is, the largest inclusion-minimal cover?   It seems fairly straightforward to show that one upper bound is $|X|$ (that is, an inclusion-minimal cover will contain at most the same number of subsets as there are elements in  $X$ itself).

But can a better bound be found?

Additional information:   No restrictions are assumed for $S$.   The bound would ideally be expressed in terms of one or more properties of $S$ (in whatever form those might take).

A conjecture: If $\min |s_i| = k$, then $\max |c_i|$ (the size of the largest inclusion-minimal cover) is bounded above by $|X| - k + 1$.  This is based upon two observations:

(1) In constructing any inclusion-minimal cover, we start with any element from $S$ (call it $s_{1'}$).  As $s_{1'}$ covers a particular subset of elements from $X$, the next added cover element (call it $s_{2'}$) must cover at least one new element from $X$ not covered by $s_{1'}$.

(2) If $\min |s_i| = k$, then we can choose the first element $s_{1'}$ in our cover to have size $k$.  This leaves $|X| - k$ elements in $X$ left uncovered. By the first observation, each additional $s_i$ must cover at least one new element in $X$, so we can add at most $|X| - k$ additional elements to the cover, leading to a cover size at most $|X| - k + 1$.

As noted in the comments, this type of bound might not be significantly smaller than $|X|$ itself.  However, I am hoping to use this in a combinatorial context, so any savings helps.  Even smaller bounds would still be useful.

The trivial bounds are that $|c| \le |X|=n$ and $|c| \le |S|=p$.

Knowing bounds on the sizes of the sets $s_i$ doesn't help much.  For instance, consider the family of sets $s_1,\dots,s_{n-k+1}$ given by $s_i=\{i,n-k+2,\dots,n-1,n\}$.  These sets are all of size $k$, and yet the largest inclusion-minimal cover has size $n-k+1$, i.e., exactly equal to the trivial bound of $|S|$ and fairly close to the trivial bound of $|X|$.  So, knowing only the sizes of the sets does not help to provide upper bounds that are much better than the trivial ones.


Looking for a subjective ranking algorithm I'm interested in learning about ranking algorithms that sort items based on preference. For example: If a person was food taster/judge and had 10 small bowls of chili that they had to rank in order from best to worst, in what way should the judge taste the chili from the individual bowls to complete the task of ranking with as small a number of repeat tastings of the same bowl as possible? The initial approach I thought of was as follows. I've named the bowls A - J:
initial order:

A, B, C, D, E, F, G, H, I, and J

Taste A then taste B. If B is better than A, switch them around in the order.
Judge thinks B is better than A:

B, A, C, D, E, F, G, H, I, and J

Taste A then taste C. If C is better than A, switch them around in the order.
Judge thinks C is better than A:

B, C, A, D, E, F, G, H, I, and J

Already though there is a problem. What if C was also better than B? We could complete the process then repeat again but its not clear to me how many times the process would have to be repeated in order to have everything ranked properly. What kinds of algorithms are these? Where can I learn more about them. Thanks.

Analytic hierarchy process (AHP) is a way to maximize or minimize or rank or prioritize things which are given in data formulated as qualitative comparisons, like a customer likes A more than B and so on. Given a set of customers and all their preferences, AHP can provide the max or a 'best' ranking or something like this.
See: https://en.wikipedia.org/wiki/Analytic_hierarchy_process


Find non-regular $L$ such that $L \cup L^R$ is regular? I've been studying for an exam I have tomorrow, and I was looking through some previous sample exam questions, when I came across this problem:

  Give a non-regular language $L$ such that $L \cup L^R$ is regular.

I've been sitting here and thinking and thinking, and I can't seem to come up with a situation where this is valid. I've determined a few things based on my understanding of non-regular languages, as well as the problem itself:

$L$ must be infinite.
$L$ must involve some kind of counting.
$L$ must contain multiple letters (i.e. it cannot be composed of entirely $a$s).

Given this, I went through a few basic possibilities:

$a^ib^i$ : This would result in $L \cup L^R$ being irregular also.
$(ab)^i(ba)^i$ (or something else palindromic) : Again, this would result in $L \cup L^R$ being irregular also. (Any palindrome would, as $L = L^R$.)
$a^pb^q$ (where $p$ and $q$ are prime) : This, too, would result in $L \cup L^R$ being irregular also, though it would be a very much broader language, which I think is a step in the right direction.

After I got this far, I think the key is in creating some language that, when unioned with itself, forms something akin to $a^*b^*$ or $(ab)^*$. The broader the words within the language, the easier it seems to define. But I can't seem to quite wrap my head around doing this.

Does anyone have a hint/spoiler or possible solution to this?

(NB: My professor does not post solutions.)

Hint: try to come up with a language $L$, such that $L \cup L^R = \Sigma^*$.

Hint2:

   Try to think on complements of known non-regular languages.

Solution:

   Let $C = \{a^nb^n \mid n>0\}$, and define $L$ to be all the strings EXCEPT for those in $C$. That is, $L = \Sigma^*\setminus C$. It is easy to see that $L$ is not Regular (closure under complement). Now let's think about $L^R$. It contains all the strings in $\Sigma^*$, EXCEPT for strings of the form $b^na^n$.
 Finally, $L\cup L^R = \Sigma^*$. Strings of the form $a^nb^n$ are not in $L$ but they are in $L^R$. Strings of the form $b^na^n$ are not in $L^R$ but they are in $L$.. al the rest of the strings appear in both languages.
 Since $\Sigma^*$ is regular, we are done.


Is Bounded Waiting satisfied for this 2 process Solution? This is my new post linked with my previous post.

Is bounded waiting satisfied in the 2 Process Solution?

The answer in that post was very useful and cleared many concepts, but I just want to apply that answer for this example, that how BW works here .

Especially, I want to know this definition works for this example.

  Define $k$-bounded waiting for a given mutual exclusion algorithm to
  mean that if $D_A^j \to D_B^l$ then $CS_A^{j} \to CS_B^{l+k}$.

Here, the Question comes

  What can be said bout the Bounded Waiting of this 2 process solution"

<------- P1 ------->

While(True)
{
    acquire(lock1)
    acquire(lock2)
        withdraw(from, amount)
        deposit(to, amount)
    release(lock2)
    release(lock1)
}

<-------- P2 -------->

While(True)
{
    acquire(lock1)
    acquire(lock2)
        withdraw(from, amount)
        deposit(to, amount)
    release(lock2)
    release(lock1)
}

In the following, I treat the first two statements acquire(lock1) acquire(lock2) as "trying", the middle two statements withdraw(from, amount) deposit(to, amount) as the "critical section", and the last two statements release(lock2) release(lock1) as "exiting".

This algorithm does not satisfy the bounded waiting property. Consider the following execution: $P_1$ and $P_2$ simultaneously execute acquire(lock1) and $P_1$ wins. $P_1$ acquires lock2 successfully, enters the critical section, and then exit by releasing locks. Now, $P_1$ and $P_2$ contend on acquire(lock1) again and $P_1$ wins again .... In this way, $P_2$ is actually starved.


Is finding cache size possible with information given? An 8-way set-associative cache is used in a computer in which the real memory size is 222 bytes. The line size is 16 bytes, and there are 26 lines per set.
A) What is the size of the cache in bytes?

What I (think) I understand:
Cache line and cache block are synonymous.
The textbook says that an n-way set-associative cache has n blocks(lines) per set. That conflicts with the next sentence that says "there are 26 lines per set." Is this problem incorrect or are my assumptions wrong?

An n-way set associative cache can store n different entries for a given index in the cache array.  So the 8-way acts like an 8x multiplier as compared with a direct mapped cache (1-way set associative).

So, I would take it that the line size of 24 with 26 lines per set and 23-way set associative is 213 or 8k bytes.

A next question might be how big are the tags that are stored in the associations?   22 (from the address space) - 4 (for cache line size) - 6 (the number of entries in the array), means that a tag size of 12 bits is needed.


Number of operations performed in increment operators How many operations are performed in the following in order to get a running time function of an algorithm:

x = x + 1
x += 1
x++

I know that in (1) there are 2 operations: an assignment and an addition.

Does the same criteria apply to (2) and (3)?

Depends. For the purpose of formal analysis, this is usually below our threshold of modelling. Just make a reasonable assumption, or forbid syntactic sugar in your model syntax.

Note that, if you are analysing at this level of detail, working with higher-level languages can be painful. If you want to follow Donald Knuth's lead,

fix a (manageable) machine model and
fix a low-level machine language.

The express your algorithms and this language and analyse. They may not look as nice as high-level pseudocode versions, but analysis is unambiguous.


How to prove Transitive property of Reducibility with a TM? How can we prove that $h(x) = g(f(x))$ is a reduction function for $A \leq_m C$,

if $f$ is the reduction function of  $A \leq_m B$ and $g$ is the reduction function for  $B \leq_m C$

The given Proposition is: $A \leq_m B, B \leq_m C \Rightarrow A \leq_m C$

I was thinking about using $HALT_{TM}$ for A. So on input $\langle M, w\rangle \in A$ if and only if $\langle M'',w'' \rangle \in  C$

The output of A would be $ \langle M', w' \rangle$ and the output of B would be $\langle M'',w'' \rangle$

If the constructed $M$ rejects the input $x$, then it loops forever, so $C$ is not recursive if $A$ is not recursive

If this isn't sufficient, then what am I missing?

The properties that reductions have are:

They preserve language membership (or Yes-instances, or whichever phrasing you prefer).
They are computable.

So then given that you have two reductions $f$, which takes instances of $A$ and produces instances of $B$ such that $x \in A \Leftrightarrow f(x) \in B$, and $g$ which does the same for $B$ and $C$, you need to show:

$x \in A \Leftrightarrow g(f(x)) \in C$.
$f\cdot g$ is computable.

The first should be a fairly straightforward application of basic logic. The second is also easy.

You can't just take $A=HALT_{TM}$ though, as all you would show then is that $HALT_{TM} \leq_{m} C$, whereas your question (appears) to ask for a proof of the transitivity of many-one reductions in general. (As a comparison would showing that $(10^{100} < b) \wedge (b <c) \Rightarrow (10^{100} < c)$ show that $(a < b) \wedge (b <c) \Rightarrow (a < c)$?)


How should I "read" a dereference operator? For example, when I look at some code like

int x = 1;
int * y = &x;

I can read it like

x equals 1
y equals the address of x

but how would I "read" something like

*y = 1;

My best guess is

The value at address y equals 1

But I'm wondering if there's a better way to think about it.

I always read
*y =1
as: assign the value $1$ to the memory location pointed by y.

Why?

y is a pointer type variable, so it has an address as a value. It another words, it points to this address. When we want to, indirectly,  manipulate the memory area pointed by y we use *y. Hence *y=1 tells that the value $1$ should be stored in the memory location pointed by y.


Can the perceptron classifier achieve perfect accuracy, on any data set? I was thinking. Since any data can become linearly seprabale through kernel methods, meaning there is a dimension where this data is linearly seprable, so feed this processed data set into the perceptron algorithm and then it might get to 100 percent accuracy.
Am I correct?

The use of a nonlinear kernel never gives any guarantees to make any data set linearly separable in the higher dimensional feature space. Kernels are used to map the data from input space onto a higher dimensional space, in which a hyperplane will be better at separating the data (but no guarantee for linear separable higher dimensional mapped data). That is why we can not be sure that perceptron algorithm will work correctly on higher dimensional mapped dataset or not.


Complexity of polynomial interpolation Polynomial Interpolation in the general case is $O(n^2)$ time complexity, but it can be done better in particular situations. For instance, when the polynomial can be evaluated at the complex roots of unity, it can be interpolated in $O(n\log n)$ time with the Fast Fourier Transform. Or at least, that's the only situation that I am aware of that can be done better than $O(n^2)$.

Are there any other forms of input that can be interpolated in better than $O(n^2)$ time?

I am particularly interested in knowing whether or not there is an algorithm that interpolates a polynomial from evenly spaced points (in the x-coordinate that is) that beats $O(n^2)$, because I think I've come up with something that does it in $O(n\log n)$ time.

Fast polynomial interpolation and Fast polynomial evaluation are algorithms that seem to be discovered back in 1973. They allow to interpolate/evaluate polynomial at N arbitrary points as far as field has 2N (?) roots of unity. Both are based on Fast polynomial division. All three are $O(n\log^2 n)$ time.

Currently they are taught at university courses and I downloaded a lot of lecture notes some time ago. Unfortunately, most links are now dead. So you can download my archive from https://mega.nz/#!ugYRXIYB!T_0cKabvJpZmBNN7ym98nofPIOksqTN5XFxToSKj9Zg

Or read the only course still available at the old address:
http://people.csail.mit.edu/madhu/ST12/scribe/lect06.pdf
http://people.csail.mit.edu/madhu/ST12/scribe/lect07.pdf

Or just look for up-to-date notes among google search results of 1, 2 and 3. Or, yeah, try to understand the original paper.


Why do most books say that a 1 bit branch predictor mispredicts on the first loop iteration? I am reading two books, Computer organization and design by David A Patterson, and Digital Design and Computer Architecture by Harris and Harris. These books claim that a 1 bit branch predictor mispredicts on the first and last iterations of every loop.
I don't understand why it mispredicts on the first iteration. I think that the first prediction result depends on the history of the CPU, so we don't know whether the predictor would predict correctly or not.
My question is whether I have to assume that the initial state of the 1 bit predictor is for the branch to be taken.

I believe the assumption is that the loop has been encountered previously (i.e., assuming a long-running program with the loop encountered multiple times and assuming no aliasing in the branch predictor), so the first iteration has the predictor set based on the last iteration of the previous encounter (i.e., not-taken) and, of course, the last iteration has the predictor set based on the previous iteration (i.e., taken).  This results in two mispredictions.

In general, a one-bit branch predictor will have two mispredictions per instance of unusual branch direction; first for the unusual instance and second for the instance immediately after that unusual instance.  By providing some form of hysteresis (as with a 2-bit predictor) or resistance to change (e.g., by randomly dropping misprediction information, possibly with probabilities determined by static branch prediction--so far as I know, a technique that is only theoretical), such unusual branch behavior is less likely to cause mispredictions for the usual behavior of a branch.


Is it decidable for a NPDA to halt? I know that it is decidable for an NPDA to accept a string $w$, i.e. a TM can receive as input the description of an NPDA along with a string and test if the NPDA accepts the string.

But are there languages where given an NPDA description as input, the TM may not halt, i.e. since the simulated NPDA also does not halt...

The (non)halting condition for PDAs doesn't make much sense; "non-halting" for a PDA means that there are one or more $\epsilon$-moves (not input read) that can cause a "loop" or an infinite stack expansion.

In order to test if a PDA accepts a string $x$, a Turing machine should not "barely simulate" it  (i.e. recusively enumerate all reachable (partial input,stack content,state) configurations of the PDA. Otherwise such machine could never end if the PDA doesn't accept the string and it contains $\epsilon$-moves.

In order to test if a PDA accepts $x$ it you should build the equivalent CFG anc check if the CFG generates the string $x$.

Also note that for any PDA $A$ there is an equivalent (costructible) PDA $A'$ with no $\epsilon$-moves (real-time PDA, i.e. the PDA reads a letter from its input every step) and even there is an equivalent $A''$ with no $\epsilon$-moves and only one state (simple real-time PDA). See Greibach normal form.

A TM once constructed $A'$ (or $A''$) can barely simulate it, enumerating all the possible nondeterministic choices, but in this case it will surely halt.


Closed-Form Expression for Recursive Function Let $k \in \mathbb{N}$ and $m \in \mathbb{R}$. Consider the following function $S\colon \mathbb{R} \times \mathbb{N} \to \mathbb{R}$:
  $$
S(m,k) = \begin{cases} 3m & \text{if } k = 0, \\ 4S(\tfrac{m}{2},k-1)+3m & \text{if } k \geq 1. \end{cases}
$$
  Find a closed-form expression for $S(m,k)$ using repeated substitution.

  Prove the correctness of the expression you obtained.

When using repeated substitution, I found the formula
$$ \sum_{i=0}^{k} 4^i\frac {3m}{2^i}, $$

whereas the solution has the formula,

$$ 6m2^k - 3m.$$

I wrote my sum (as well as the original recurrence relation) in Python, and plugged in values from 0 to a 100 for both $m$ and $k$.

For some reason, the sum gets wrong values starting at $m, k = 47, 47$, and follows a weird pattern after that.

Does anyone have any idea what is going on?


Pumping lemma for simple finite regular languages Wikipedia has the following definition of the pumping lemma for regular langauges...

  Let $L$ be a regular language. Then there exists an integer $p$ ≥ 1
  depending only on $L$ such that every string $w$ in $L$ of length at
  least $p$ ($p$ is called the "pumping length") can be written as $w$ =
  $xyz$ (i.e., $w$ can be divided into three substrings), satisfying the
  following conditions:

  |$y$| ≥ 1
  |$xy$| ≤ $p$
  for all $i$ ≥ 0, $xy^iz$ ∈ $L$

I do not see how this is satisfied for a simple finite regular language. If I have an alphabet of {$a,b$} and regular expression $ab$ then $L$ consists of just the one word which is $a$ followed by $b$. I now want to see if my regular language satisfies the pumping lemma...

As nothing repeats in my regular expression the value of $y$ must be empty so that condition 3 is satisifed for all $i$. But if so then it fails condition 1 which says $y$ must be at least 1 in length!

If instead I let $y$ be either $a$, $b$ or $ab$ then it will satisfy condition 1 but fail condition 3 because it never actually repeats itself.

I am obviously missing something mind blowingly obvious. Which is?

You are right - we cannot allow "pumping" words of a finite $L$. The thing you are missing is that the lemma says there exists a number $p$, but does not tell us the number.

All words longer than $p$ can be pumped, by the lemma. For a finite $L$, it happens so that $p$ is larger than the length of the longest word in $L$. Thus, the lemma only holds vacuously, and cannot be applied to any word in $L$, i.e., any word in $L$ does not satisfy the condition of "having length at least $p$" as the lemma requires.

A corollary: if $L$ has pumping length $p$, and there exists some word $w\in L$ of length at least $p$, then $L$ is infinite.


Graph splitting via an algorithm and proof of properties Given the following function:

function split(G)
    if (all vertices of G have even degree) then
        return (V (G), ∅)
    else
        Let a ∈ V be a vertex of odd degree;
        S ← NG(a);
        G ← G − a;
        for ((∀)u, v ∈ S, u != v) do
            if (uv ∈ E(G)) then
                E(G) ← E(G) − uv;
            else
                E(G) ← E(G) ∪ uv;
        (W1, W2) ← split(G);
        if (|W1 ∩ S| % 2 = 0) then
            V1 ← W1 ∪ {a};
            V2 ← W2;
        else
            V2 ← W2 ∪ {a};
            V1 ← W1;
return (V1, V2)

I have to show that V1∩V2 = ∅, V1∪V2 = V(G) and the subgraphs of G obtained from V1 and V2 have an even degree on all vertices.

Now, based on the function it is obvious that the properties stated above hold true, but I am stumped as to how exactly should I go about proving them and by what general rule or criteria the split function splits the graph(I have no problem following the algorithm but the "big picture" escapes me).

EDIT: NG(a) Is the set of a's neighbours.

I'll give you the schema of the proof. You'll have to fill in the blanks on your own. The idea is to prove by induction the following property $P(n)$:

  On a graph $G$ having $n$ vertices, the function $\mathrm{split}(G)$ terminates and returns a partition $V_1,V_2$ of the vertex set of $V$ such that in the subgraphs of $G$ induced by $V_1$ and $V_2$, all vertices have even degree.

First you have to prove the base case $P(1)$. That's quite easy.

Now, for every $n$ you have to prove that $P(n)$ implies $P(n+1)$. To do this, you analyze what happens when $\mathrm{split}$ is run on a graph $G$ having $n+1$ vertices. There are two cases: if all degrees in $G$ are even then it is easy to see that $\mathrm{split}(G)$ terminates with an appropriate partition. Otherwise, $\mathrm{split}$ creates a graph $G'$ on $n$ vertices and runs itself on $G'$. Since $G'$ has $n$ vertices, the induction hypothesis implies that $\mathrm{split}(G')$ with a partition $V'_1,V'_2$ of the vertex set of $G'$ such that the subgraphs of $G'$ induced by $V'_1,V'_2$ have only even degrees. The procedure $\mathrm{split}$ uses $V'_1,V'_2$ to create a partition $V_1,V_2$ of the graph $G$. It thus clearly terminates. To finish the proof, you have to show that the subgraphs of $G$ induced by $V_1,V_2$ have all even degrees.

This is the structure of the proof. All you have to do now is to fill in the blanks.


NP-hard - Definition The definition of NP-hard problem in Wikipedia is :
NP-hardness (non-deterministic polynomial-time hard), in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP".

There are NP-hard problems not in NP class. My question (more curiosity) concerns the NP in the definition. Since a NP-hard maybe is not in NP class, why we call it NP-hard?

When we say we have a NP-complete problem, then this problem is indeed in NP class.

Here is a definition which describes the relationship between hard and complete:

  Given a set C of problems and a reduction R, it is natural to ask if there are problems Π ∈ C such that any problem Π′∈C,  R-reduces to Π. Such “maximal”
  problems are called in complexity theory complete problems. Let C be a class of
  problems and R be a reduction. A problem Π ∈ C is said to be C-complete (under R-reduction) if for any Π ∈′ C, Π′ ≤R Π. A C-complete problem (under reduction R) is
  then (in the sens of this reduction) a computationally hardest problem for class C. For instance, in the case of NP-completeness, NP-complete problems (under Karp-reduction) are the hardest problems of NP since if one could polynomially solve just one of them, then one would be able to solve in polynomial time any other problem in NP. Let C be a class of problems and R a reduction. A problem Π is said to be C-hard (under R-reduction)
  if for any Π ∈′ C, R Π≤ Π ′. In other words, a problem Π is C-complete if and only if Π ∈ C and Π is C-hard.

References

An Overview on Polynomial Approximation of
NP-Hard Problems
Computers and Intractability: A Guide to the Theory of NP-Completeness


What is the benefit of using one to one thread mapping model instead of Many to Many or two level? So in the silberschatz O.S book it says Windows uses one to one model (mapping user level threads to kernel level threads)

but why? i thought many to many and two level models are much better, specially two level model, so why not use the two level mode or many to many? whats the benefit compared to other models and isn't there some overhead and limitation(like number of threads) because of using one to one?

overall, if someone wants to create a new O.S, how should he know which model to choose?

I am gonna be very careful here and say it is due to complexity of managing threads at two different levels did not produce the expected results, the lack of a direct mapping caused issues meeting POSIX threads requirements. Notice that in the book it says that Solaris 8 and before have implemented many to many model. Here you can see the document they "explain" the retirement of this model.

  The Solaris 9 Operating Environment does not include an alternate threads implementation. The
  old MxN implementation has been gracefully retired and replaced with an enhanced version of
  the 1:1 implementation. The /usr/lib/lwp directories which held the alternate library in Solaris 8
  software have been preserved, but these now simply link back to /usr/lib.
  Extensive testing indicates that this decision should cause no issues for existing applications.
  Most applications are expected to benefit from this move and binary compatibility is preserved.

Again, sadly, there was nothing concrete stated as reason, but my guess will be complexity.


distance between histograms I have 2 histograms that represent the height of characters in 2 images.
example:

1 **
2 ****
3 ****
.
.
.
100 ******

For these 2 histograms I compute the peaks. And To check if these 2 images are similar I compute the interseciton between the indices of the 2 images.
Example:
For image 1 the indices of the peaks are 1, 10 and 13
for image 2 the indices of the peals are 1,10, 14.
Image1 Inter Image1 = 2 So these images are similar.

But I feel that the intersection is not enough. I think that i should also use the size of the buckets of the histograms peaks.

Is there  a way to use to both of them to measure the similarity in 1 function So that I can have a stable similarity function?

If you normalize your histograms you then have an empirical pmf. There are numerous methods to calculate distances of pmfs, such as Kullback-Leibler and Jensen-Shannon divergences. If the base-set of the histograms are exactly the same then KL divergence will work fine. If they intersect, but are not exactly the same, then JS divergence will work instead.

Be careful as KL divergence is non-symmetric. That is, given two pmfs $P$ and $Q$, $\text{D}_{\text{KL}}(P||Q)$ may not be equal to $\text{D}_{\text{KL}}(Q||P)$. On the other hand $\text{D}_{\text{JS}}$ is symmetric, but still not a metric.


Making a conjecture of a closed form There's a formula given $$
 T(m,n) = \left\{
  \begin{array}{l l}
    1 & \quad \text{if $m=0$}\\
    1+T(n \mod m, m) & \quad \text{if $m>0$}
  \end{array} \right.$$
We're told to use repeated substitution to make a conjecture about a closed form for $T(F(n),F(n+1))$, where $F(k)$ is the $k^{th}$ Fibonacci number.This is a practice question and I have no idea how to start. Could someone help?

For $F_0 = 0, F_1 = F_2=1, \dotsc$ consider

$$
\begin{align}
T(F_n, F_{n+1}) &= 1+T(F_{n+1}\mod{F_n}, F_n) & \text{by definition}\\
 &= 1+T(F_{n-1}\mod{F_n}, F_n) & \text{since }F_{n+1} = F_n+F_{n-1}\\
 &= 1+T(F_{n-1}, F_n) & \text{since }F_{n-1} \le F_n\\
\end{align}
$$
continuing, we see
$$
\begin{align}
T(F_n, F_{n+1}) &= 1+T(F_{n-1}, F_n)\\
 & = 2 +T(F_{n-2}, F_{n-1})\\
 & = 3 +T(F_{n-3}, F_{n-2})
\end{align}
$$
and in general
$$
T(F_n, F_{n+1}) = k+T(F_{n-k}, F_{n-k+1})
$$
so when $k=n$ we have
$$
T(F_n, F_{n+1}) = n+T(F_0, F_1) = n+T(0, 1) = n+1
$$
Now to make a conjecture about the growth of $T(F_n, F_{n+1})$ we need to find how large $n+1$, the run time, will be in terms of the size of $F_{n+1}$. There is a closed form for this, namely
$$
F_k = \frac{\phi^k-\psi^k}{\sqrt{5}}
$$
where $\phi = (1+\sqrt 5)/2\approx1.618$ and $\psi = (1-\sqrt 5)/2\approx-0.618$. Since $|\psi|<1$ that term will be negligible for sufficiently large values of $k$ so we have $F_k\approx \phi^k/\sqrt5$. Taking the log (to the base $\phi$) of both sides, we have $\log{F_k}\approx k-\log{\sqrt5}$, so $k$ will be $\log {F_k}$ plus a constant which we can ignore. In terms, then, of its arguments, $p, q$, with $q \ge p$ we'll have our conjecture:
$$
T(p, q) = O(\log q)
$$
which happens to be true, even if we don't restrict ourselves to Fibonacci numbers for the arguments.

This function is just the timing function for the Euclidean algorithm, which finds the greatest common divisor of the arguments:

gcd(p, q) =
   if p = 0
      return q
   else
      return gcd(q mod p, p)

For instance,
$$
\gcd(15, 24) = \gcd(9, 15) = \gcd(6, 9) = \gcd(3, 6) = \gcd(0, 3) = 3
$$
after five recursive calls. It happens that the longest this algorithm will take to complete is when the arguments are consecutive Fibonacci numbers. The upshot is that, fortunately for us this is fast, being no worse than proportional to the number of digits in the arguments.


Why is the vulnerable time in pure aloha twice the frame time? The time required to send a frame is called frame time.
Vulnerable time is the time during which no transmission should be done to avoid any collision.

My question is what kind of problem will be created if vulnerable time was equal to frame time?

This is because in pure ALOHA, even if a bit of a frame collides with a bit of another frame, both the frames get discarded. Also, in pure ALOHA, a station doesn't listen to the medium before transmitting. So, it has no way of knowing that another frame was already underway. If another frame was indeed underway already, then the newly transmitted frame becomes vulnerable. That is why it is called "vulnerable time". It equals twice of the frame time because it counts the time in which the transmission of another frame should start so as to make the current frame vulnerable. This time interval includes:

the frame time because if transmission of another frame were started in the frame time of the current frame, collision would occur.

a time interval (equal to the frame time) before the frame time because if transmission of another frame were started in this time interval, collision would still occur.

My question is what kind of problem will be created if vulnerable time was equal to frame time?

If the vulnerable time were equal to frame time, any frame (say A) transmitted prior to the considered frame (say B) could be transmitted within the frame time of the considered frame (B), resulting in a collision.
Suppose a sender X starts transmitting at time instant '0' and finishes at instant 't'. Then any other sender Y should start at or after instant 't' and continue till instant '2t' (because if Y start its transmission even a tiny amount of time before 't', there will be collision). Here, the vulnarable time for the frame transmitted by Y is the sum of its own frame time (i.e. 't' to '2t') and another time duration (i.e. '0' to 't'), effectively being '0' to '2t'. This is the time interval during which no sender should send on the channel to ensure that the frame sent by Y doesn't collide.


Index variable takes up log(n) space? In the definition of in-place algorithm, from Wiki, " However, this form is very limited as simply having an index to a length n array requires O(log n) bits."
How does an array index requires log n bits?
For example, A[0], 0 here just take O(1) bits, right? It is just 1 number.
I guess my question is about how an array establish its index.
An array of size n has n space for its elements, and n space for storing the index numbers 0,1,2...
I assume I am wrong, but I don't know how.

If you have a variable $x$ that can represent any number from $0$ to $n-1$ (or any value from a set of of $n$ possible values, really), such an the index of an array of $A[0 \dots n-1]$ of $n$ elements, then $x$ needs to use at least $\lceil \log_2 n \rceil = \Omega(\log n)$ bits.
This is because there are $2^b$ combinations for the values of $b$ bits. Then, to represent $n$ values you need to have $2^b \ge n$, i.e., $b \ge \log_2 n$. You can add the ceiling since $b$ must be an integer.
When you say "an array of $n$ elements uses $O(n)$ space" you are probably  thinking of a word-RAM model. Here the memory is split into addressable words, i.e., groups of $w$ bits. Each entry in the array occupies one (or a constant number of) words of memory (this also means that the elements in the array can't represent more than $2^{\Theta(w)}$ values each).
Usually the word size $w$ is chosen to be $\Theta(\log n)$, where $n$ is some natural parameter of the input problem (e.g., the size of the instance). In this case an index of an array of $n$ elements can be stored into a single memory word, i.e., in $O(1)$ space.
However this is not contradicting the above lower bound of $\lceil \log_2 n \rceil$ bits, it's just that these bits are all packed into a single (or into a constant number of) memory word(s).


Maximum weight matching There are polynomial time algorithms to find maximum weighted matching in a general graph. Is there any algorithm that also handles negative weights in the general graph and find maximum weighted matching for that graph with negative weights ?

I was only familiar with the Hungarian algorithm which only works for bipartite graphs but I've found something that claims to work for general graphs as well.
The basic algorithm is the blossom algorithm, but since you need to find the maximum weight matching you will need Kolmogrov's Blossom V which is based on it.


Find all substrings that fit the mask with asterisks There is a problem.

Given string $text$ containing only letters and string $mask$ containing letters and asterisks (*), where asterisk means substitution of zero or more letters, find all substrings of $text$ that fit $mask$.

There is an example: let's $text=cabccbacbacab$, $mask=\textbf{ab}*\textbf{ba}*\textbf{c}$. The algorithm should give substrings $abccbac$, $abccbacbac$, because $abccbac = \textbf{ab} + cc + \textbf{ba} + \textbf{c}$, $abccbacbac = \textbf{ab} + ccbac + \textbf{ba} + \textbf{c}$.

I have tried to split mask into tokens (for above example $\textbf{ab},\textbf{ba},\textbf{c}$) then find all occurrences of every token in $text$ then make cartesian product of all relevant occurrences and check every token for condition.

Is there more efficient solution for this problem?

Yes, there is a more efficient algorithm.  Your algorithm can take exponential time.

You can check whether there exists any match in $O(nm)$ time, where $n$ is the length of text and $m$ is the length of mask, and find all matches in $O(n^2m)$ time.  I'll show two solutions, one using dynamic programming and one using graph search.  You can pick whichever you find easier to understand.

I don't know whether you can do even better.

Dynamic programming

Build an array $A[i,j]$, where $A[i,j]$ is true if some prefix of $\text{text}[i..n]$ matches $\text{mask}[j..m]$.  There's a recursive formula for $A[i,j]$:

$$\begin{align*}
A[i,j] &= \text{True} \qquad &&\text{if } j=m+1\\
A[i,j] &= A[i+1,j+1] \qquad &&\text{if } \text{mask}[j]=\text{text}[i]\\
A[i,j] &= A[i,j+1] \lor \cdots \lor A[n,j+1] \qquad &&\text{if } \text{mask}[j]=*\\
A[i,j] &= \text{False} \qquad &&\text{otherwise}
\end{align*}$$

If you fill this in, in the usual way, you get a $O(nm^2)$ time algorithm.  If you additionally keep track of $B[i,j] = A[i,j+1] \lor \cdots \lor A[n,j+1]$ and fill in entries in the right order, you get a $O(nm)$ time algorithm.

Once you have filled in the matrix, you can find all substrings of text that match: each entry $A[i,1]$ that is true corresponds to one or more substrings of text that match (the substring starts at index $i$ of text).  You can adapt the above algorithm to enumerate all those matching substrings by repeating the above computation once per possible ending place of the match.

There may be even faster methods, using ideas from string matching and/or regular expression matching.

Graph search

Build a directed graph on $nm$ vertices.  Each vertex is of the form $\langle i,j \rangle$, which we think of as corresponding to the problem of checking whether some prefix of $\text{text}[i..n]$ matches $\text{mask}[j..m]$.  Now add the following edges:

Add the edge $\langle i,j \rangle \to \langle i+1,j+1 \rangle$ if mask$[j]$ = text$[i]$.
Add the edge $\langle i,j \rangle \to \langle i,j' \rangle$ if mask$[j] = *$ and $j' > j$.

Finally, mark each vertex $\langle i,m+1 \rangle$ as "accepting".

This is a directed acyclic graph; it has no cycles.  Now, for each $i$, find all accepting vertices that are reachable by some path starting at the vertex $\langle i,1 \rangle$.  If $\langle i',m+1 \rangle$ is reachable from $\langle i,1 \rangle$, that means that the substring text$[i..i'-1]$ matches mask, so you can output this substring.   This computation can be done in $O(nm)$ time per starting point using breadth-first search, for a total of $O(n^2m)$ time.


Can we say anything about the complement of a regular language? Given a regular language $L$, can we say anything about its complement $\overline L$? One thing that is trivial to say is that the DFA's for both languages are equal in size as complementing the language is simply a matter of changing all accepting states into rejecting states and vice-versa. Are there any other things to conclude? Is there anything one can say about the number of states of a (minimal) NFA?

Complementing an NFA may involve an exponential blowup.
While there are concrete examples for this, it can also be deduced (in a way) by the fact that NFA universality is PSPACE complete. Indeed, if complementing an NFA could be done in polynomial time, then universality would also be possible in polynomial time.
This is not exact, since complemetation could also be only sub-exponential, but not polynomial.
As for a concrete example: Let $p_1,p_2,\dots$ be an enumeration of the prime numbers.
Consider the language: $L_k=\{1^n: \exists 1\le i\le k\ \text{ s.t. }\ p_i \not\mid n\}$. It is easy to construct an NFA for $L_k$ with $\sum_{i=1}^kp_i$ states.
However, it is also not hard to prove that a minimal NFA for $\overline{L_k}$ needs $\prod_{i=1}^k p_i$ states, which is exponential in $\sum_{i=1}^kp_i$.


picking a word for pumping lemma for L = {a^n b^m c^n b^m a^n | m,n≥0} If i have a language like $L = \{a^n b^m c^n b^m a^n \mid m,n\ge0\}$

when i pick a word for the language, would it be correct if i pick any of

these words: $w = a^k c^k$, $w = a^k b^m c^k $, $w = b^m  b^m$,   $w = b^m c^n b^m$.

If you want to apply the pumping lemma for regular languages, you can pick any word in the language whose length is no less than the pumping length. The same applies to the pumping lemma for context-free languages.

However, some of the words in your list may not be in the language.

$a^k c^k$ is in the language if and only if $k=0$.
$a^k b^m c^k $ is in the language if and only if $k=0$ and $m$ is even.
$b^mb^m$ is always in the language.
$b^m c^n b^m$ is in the language if and only if $n=0$.

Yes, a general approach is to check the balance between different symbols. Had the language been $\{a^nc^n\mid n\ge0\}$ or $\{a^n b^m c^n b^m\mid m,n\ge0\}$, you could select $a^kc^k$ towards a contradiction. You cannot if the language is $\{a^n b^m c^n b^m a^n \mid m,n\ge0\}$, since $a^kb^k$ is not a word in the language in the first place. For that language, you can choose $a^kc^ka^k$.

Specifically, here are all the words in $\{a^n b^m c^n b^m a^n \mid m,n\ge0\}$. Note that all of them start and end with the same symbol.

$$\begin{align}
&\epsilon,\\
&aca,\ a^2c^2a^2,\ a^3c^3a^3,\ a^4c^4a^4,\ \cdots\\
&bb,\ a^1bc^1ba^1,\ a^2bc^2ba^2,\ a^3bc^3ba^3,\ a^4bc^4ba^4, \cdots\\
&b^2b^2,\ a^1b^2c^1b^2a^1,\ a^2b^2c^2b^2a^2,\ a^3b^2c^3b^2a^3,\ a^4b^2c^4b^2a^4,\ \cdots\\
&b^3b^3,\ a^1b^3c^1b^3a^1,\ a^2b^3c^2b^3a^2,\ a^3b^3c^3b^3a^3,\ a^4b^3c^4b^3a^4,\ \cdots\\
&\vdots
\end{align}$$


What is a "special sequence" in EBNF? In Extended Backus-Naur Form (EBNF) there is one form called a "special sequence" which is surrounded by questions marks ?...?

What does this mean?

Quoting from the Wikipedia page:

  According to the ISO 14977 standard EBNF is meant to be extensible, and two facilities are mentioned. The first is part of EBNF grammar, the special sequence, which is arbitrary text enclosed with question marks. The interpretation of the text inside a special sequence is beyond the scope of the EBNF standard.


Data Searching from a large data set without reading each element I have just started learning algorithms and data structures and I came by an interesting problem.
I need some help in solving the problem.

There is a data set given to me. Within the data set are characters and a number associated with each of them. I have to evaluate the sum of the largest numbers associated with each of the present characters. The list is not sorted by characters however groups of each character are repeated with no further instance of that character in the data set. Moreover, the largest number associated with each character in the data set always appears at the largest position of reference of that character in the data set.
We know the length of the entire data set and we can get retrieve the data by specifying the line number associated with that data set.
For Eg.
C-7
C-9
C-12
D-1
D-8
A-3
M-67
M-78
M-90
M-91
M-92
K-4
K-7
K-10
L-13
 length=15
get(3)= D-1(stores in class with character D and value 1)
The answer for the above should be 13+10+92+3+8+12 as they are the highest numbers associated with L,K,M,A,D,C respectively.
The simplest solution is, of course, to go through all of the elements but what is the most efficient algorithm(reading the data set lesser than the length of the data set)?

Say you have $n$ entries, $m$ distinct letters, and the $i$-th letter occurs $k_i$ times. You can find the last occurrence of the $i$-th letter using a variant of binary search: Double your step size until you find a different letter (or run out of the array), do binary search between your last and second-to-last step. This takes about $2\log k_i$ many steps. So in total you need about

$$\sum_{i=1}^m \log k_i = \log \prod_{i=1}^{m} k_i$$

many steps. That product is biggest when all terms are equal, so you have something like $m\log (n/m)$ many steps.

Naively implemented, this is not always better than looking at all elements though. If you work out all the details, you'll see that for example when $m=n$ you have to be a bit careful.