What is memory model in computer organization? I'm new to Computer Organization and even to this community. I didn't find anything which was simple, clear and up to the point. Any examples supporting the discussion is appreciated. I'm not looking for some text book answer.

Here's an example of my view to question: What is a Programmer's Model ?
Programmer's model shows what the CPU has available to a programmer for the execution of computer programs.
It covers the CPU resources for execution of the CPU's instruction set.
(resources like state variables, AKA registers that can affect — or be affected by — the execution of instructions)

This programmer's model would NOT detail hardware, such as how the CPU's electronic circuitry works,
how buses transport data or the I/O peripherals available.
i.e. The underlying details of how all of that is actually accomplished are hidden from the programmer.

In other words, the programmer's model would NOT cover functions that cannot be observed by CPU instructions.
[EXCEPTION: those instructions trying to detect hardware operations, such as cache behavior, read/write variances because of varying bus delays etc are excluded]

So, similarly I wish to know what is a Memory Model ?

um I'm not sure if it is what you are looking for or not. I assume by memory model you mean the part in which we place input and do some calculation (like paper which we write something to remember and calculate).

The memory model depends on the definition of the model itself. In CS we have different kinds of computing model with different power.
One of the simplest one is Deterministic Finite Automata and informally its memory just contains an input string and nothing more.
One of the most powerful one is Turing machine that its memory is a infinite tape.
There are other models between these two such as PushDown Automata and Linear Bounded Automata where loosely speaking their memories contains stack of symbols and finite tape.

Also there are other models with same power as Turing machine, like two stack PDA, cellular automata and etc.

So by how to define your computing model and program, your memory model details will be different.


DFS miniumum spanning tree Just a quick question,

If i were to alter the general DFS algorithm to do this:

minDFS(Vertex v)
{
   if (!v.getVisted())
   {
       v.setVisited();
       Vertex temp = findClosestVertex();
       graph.addEdge(v, temp);
       minDFS(temp);
   }
}

Would I eventually (at the end of DFS) get  minimum spanning tree? I know there are other ways of getting the MST (Kruskal's, Prim's etc..),but I was just wondering if this would work.

No. Consider the counterexample $C_4$

$V = \{1,2,3, 4\}, E = \{ \{1,2\}, \{2,3\}, \{3, 4\}, \{1,4\} \}$

with $c(1,2) = 1, c(2,3) = 100, c(3,4) = 1, c(1,4) = 2$.

Obviously the MST is the one ST not containing $\{2,3\}$, but if your algorithm starts at 1, it goes to 2, then to 3 and then to 4 and finds a suboptimal ST containing $\{2,3\}$.

The main problem of your algorithm is that it always computes a path (i.e if there is no path of length $|V| - 1$ your algorithm can terminate without finding a ST), which the MST must not always be.


Range search in a max-heap I am having trouble with coming up for a suitable algorithm for this question. A max-heap is essentially visualized as a binary tree not a binary search tree. Also the runtime of the algorithm must depend only on the number of elements in the output. I was thinking of doing a preorder traversal on the max heap. While doing the preorder traversal, if the value of a node is less than the given value x, we return to the previous recursive call. All child nodes in a max heap are less than the parent node. Otherwise we output current node and recur on the children.
I am not sure however if the runtime of this algorithm depends only on the number of elements in the output.
Anybody have other suggestions/thoughts? Thanks.

The algorithm you're describing is basically correct.
To summarize in one sentence: "If the current value is less than $x$, turn back."
The reason it has the desired time complexity is because the set of the nodes you are visiting is precisely:

the root node
all the nodes which are direct descendants of the nodes in the output (since every node has no more than two children, there are no more than $2k$ of these)

So the total number of times the body of your function gets executed is no more than $2k+1$.


Intuition for PH notation in Arora-Barak's Computational Complexity For the definition of polynomial hierarchy:

$x \in L \Leftrightarrow \exists u_1 \in \{0, 1\}^{q(|x|)}\forall u_2 \in \{0, 1\}^{q(|x|)} \cdots Q_i u_i \in \{0, 1\}^{q(|x|)} M(x, u_1, \ldots, u_i) = 1$

What does the notation of $M(x, u_1, \ldots, u_i)$ mean? The definition used for $\mathcal{NP}$ is $M(x, \alpha)$ where $\alpha$ is the certificate. What is the intuition for what the $u_i$ signify in terms of the TM $M$?

The notation $M(x,u_1,\ldots,u_i)$ stands for a polytime Turing machine with $i+1$ inputs, applied to the inputs $x,u_1,\ldots,u_i$. There are many ways of implementing Turing machines with several different inputs, and from this perspective they are all equivalent, so pick one. (Some examples: several input tapes, inputs separated by special separator symbol, oracle mechanism for obtaining $j$th input.)

Your definition is for languages in $\Sigma_i^P$. When $i = 1$, you get $\mathsf{NP}$. A language $L$ is in $\mathsf{NP}$ is we can verify that $x \in L$ using a polytime Turing machine given a polysize hint $\alpha$. If the verifier is $M$, then this means that
$$ x \in L \Leftrightarrow \exists \alpha \in \{0,1\}^{q(|x|)} M(x,\alpha) = 1, $$
where $q$ is a polynomial bounding the size of the witness.

For $i > 1$ there are more quantifier alternations, and you can think of it as a game between two players: the existential player is trying to prove that $x \in L$, while the universal player is trying to prove that $x \notin L$. The game proceeds in $i$ rounds, in which the players alternate giving polysize "witnesses" $u_1,\ldots,u_i$. After $i$ rounds, a judge $M$ is shown the transcript, and makes a verdict; $M(x,u_1,\ldots,u_i)=1$ means that the judge thinks that $x \in L$. A winning strategy for either player is a strategy that guarantees that the verdict will be favorable to them. A language is in $\Sigma_i^P$ if there exists such a polytime judge $M$ such that if $x \in L$ then the existential player has a winning strategy, while if $x \notin L$ then the universal player has a winning strategy.

Here are two examples:

$SAT \in \Sigma_1^P$. In this case the judge $M$ takes as input a formula $x$ and a witness $w$, and checks that $w$ is a satisfying assignment for $x$. If $x \in SAT$ then there is a satisfying assignment, and so the existential player can guarantee that the judge declares $x \in SAT$. If there is no satisfying assignment then the universal player (who is silent) can guarantee that the judge declares $x \notin SAT$.
Circuit minimization $CMIN \in \Sigma_2^P$: a pair $(A,k)$ is in $CMIN$ if $A$ is a circuit encoding a function $f$ which can be computed by a circuit of size at most $k$. The judge $M$ takes as input the pair $(A,k)$, a witness $B$ from the existential player, and a witness $x$ from the universal player, and accepts if $B$ is a circuit of size at most $k$ that agrees with $A$ on the input $x$. If $(A,k) \in CMIN$ then the winning strategy of the existential player is to produce a circuit $B$ of size at most $k$. If $(A,k) \notin CMIN$ then the winning strategy of the universal player is, for each circuit $B$ of size at most $k$, to find an input $x$ on which $A$ and $B$ disagree.


Variations of Depth First Travesal While learning depth first traversal, I realise there are two approaches that are followed.

Method 1. The first one is as given in the Forouzan's book is as follows:

Push the initial node onto the stack
Pop the stack
Process the popped out node
Push all its adjacent nodes onto the vertex
Go to step 2.

Method 2. Then there is a version of depth first traversal as given in CLRS:

Push the node onto the stack
Process the pushed node
Push one of its adjacent node onto the stack.
If there is no adjacent node to the stack top node, then pop it.
Go to step 2.

CLRS does not explain it in terms of push and pop operation on stack. However I made this push pop version equivalent to CLRS Depth First traversal explanation. This approach is also explained in this video.

I observe the following points:

The two versions yields different stack contents and processing sequence.
Method 1 pops out the node before pushing its neighbor. Method 2 pops out the node after all its descendants are processed.
Method 1 pushes all adjacent nodes and processes the stack top node while method 2 pushed one adjacent node, processes it, pushes its adjacent node. This results in different processing sequence, as can be seen below:

So which one is correct/preferable ?

Every DFS algorithm should also construct a DFS tree (or, in general, forest), which records how the search progresses. For the CLRS algorithm, the adjacent node in step 3 is made the child of the node in step 2. For the other algorithm you have to be more careful (I'll let you figure out the correct way). If the DFS tree is constructed properly, then it will satisfy the following property:

  If $(x,y)$ is an edge not belonging to the tree, then either $x$ is an ancestor of $y$ or $y$ is an ancestor of $x$.

This is the property of DFS used in actual algorithms. The actual sequence in which the nodes are traversed could also be important, but this is less common.

Corneil and Krueger suggest a generic "non-deterministic" version of DFS, and give a characterization in terms of the resulting DFS traversal order. They also suggest a canonical way of forming the DFS tree given the DFS order – each node is the child of its earliest neighbor, and show that the resulting DFS tree always satisfies the crucial property stated above.

If Method 1 satisfies the criterion of Corneil and Krueger, then it is worthy of the name DFS. If you are curious, you can read the paper and check whether the criterion listed there holds for that algorithm. Even if it doesn't, you can check whether there is a simple way to construct a DFS tree (not necessarily using the construction suggested by Corneil and Krueger) that satisfies the property above – that suffices in most cases.

You can use any algorithm which satisfies your needs (in some cases, you don't care about any property, only about traversing the entire connected component). A "correct" form of DFS, together with a method of constructing the DFS tree, should satisfy the DFS tree property, and preferably also the ordering characterization of Corneil and Krueger. Which one is preferable depends on many factors – usually the one using the least resources (time and memory).


How does one prove that Big Step semantics and Small Step semantics are equivalent for IMP? I know there is this paper but I wanted to do a special case proof for just IMP for fun. So the theorem is:

  $$ \langle P , \sigma \rangle \to_{Big} \langle \{ \} , \sigma' \rangle \iff \exists N \in \mathbf N: \langle P , \sigma \rangle \to^N_{Small} \langle \{ \} , \sigma' \rangle $$

in words; the program P in state $\sigma$ evaluates to the empty block IFF there exists a certain number of small step steps inference steps that arrives us to the same configuration, the empty program in state $\sigma'$. Note $\langle P, \sigma \rangle$ stands for a program configuration with state $\sigma$. I am assuming both small step and big step have the same sort of configuration, which might be a big assumption and hard to formalize in real code...

I am happy with just an outline/sketch since a rigurous proof might be too much work probably and I'd rather get something than nothing.

I want to focus on $\Rightarrow$ (big to small). I think one of my main difficulties is finding such an $N$ that works. But conceptually to me I think I would break the proof by induction on the program P. The program has 6 constructors/cases:

Empty Block {}
Block B which is just $\{ S \}$
Assignments $x = AExp ;$
Sequences $S_1 ; S_2$ where $S_i$ is a statement.
while statements $ While \ (BExp) \ do \ S $.
ifElse statements $If \ (BExp) \ do \ S_1 \ Else \ S_2 $.

for the first case 1) its simple we have $\langle \{ \} , \sigma' \rangle$ on the RHS for big step and on the LHS $\langle \{ \} , \sigma' \rangle$ for small step, which are the same configuration. Done.

3) For the case assignment case we have to show that the AExp expressed uin the semantics, say big step or small step evaluates to the same as the "aeval" function that recursively just evaluates a real arithmetic expression. Not sure how I can make this more rigorous but at least it is a start.

Things with Boolean expression in them also need the same beval equivalence with boolean evaluation equivalence in their corresponding semantics.

However when things involve statements I am honestly not sure what one would need to argue to show they are equivalent. Do we do induction again on each statement and then proceed by apply the inference rules as many times as possible and show they evaluate to the same final state and empty block? Or what does one need to do? Then especially, how does one find the $N$?

The inference rules I had in mind are just any standard IMP semantics:

http://fsl.cs.illinois.edu/images/b/b3/CS522-Spring-2011-PL-book-bigstep.pdf
http://fsl.cs.illinois.edu/images/6/65/CS422-Spring-2015-02c-SmallStep.pdf
https://softwarefoundations.cis.upenn.edu/plf-current/Smallstep.html
http://www.cs.cornell.edu/courses/cs6110/2009sp/lectures/lec05-fa07.pdf
http://web.cse.ohio-state.edu/~bond.213/6341/Operational-6.pdf
https://www.seas.harvard.edu/courses/cs152/2010sp/lectures/lec03.pdf

Don't proceed by induction on $P$, i.e. by structural induction on the syntax of programs. This is because structural induction is quite weak, and is likely to fail on while loops.

Look at the inference rules for the big step semantics for while, in particular at the while-true rule which handles the case where the guard is true. In such case, you'll see that in one of the premises we have the same while loop. Roughly, the rule defines the behaviour of while in terms of itself.

(I didn't check your own rule, and used mine instead, but it should be simple to adapt the reasoning to yours.)

$$
\dfrac{
\sigma\models \phi \quad
\langle c, \sigma \rangle \to_b \sigma'
\quad
\langle while\ \phi\ do\ c, \sigma' \rangle \to_b \sigma''
}{\langle while\ \phi\ do\ c, \sigma \rangle \to_b \sigma''}
$$

If we proceed by structural induction, when we handle such case, we only get an induction hypothesis for $c$, wince it is a subterm of $while\ \phi\ do\ c$. That however provides no help in coping with he last premise involving the $while$ itself.

The solution is to use the induction principle generated by the rules for $\to_b$, instead. Doing that, when handling the rule above, we have two induction hypotheses, namely that the small step semantics

reduces $\langle c, \sigma \rangle$ to some $\sigma'$ state in some $N$ steps
reduces $\langle while\ \phi\ do\ c, \sigma' \rangle$ to some $\sigma''$ state in some $M$ steps

Exploiting those properties, it is possible to show that, using (something like) $N+M+1$ steps, we can reduce $\langle while\ \phi\ do\ c, \sigma \rangle$ to $\sigma''$ using small steps.

The other rules can be handled in a similar way.

When you write such proofs, I strongly suggest to always check the while-true case first, since that's the "hardest". Checking it first helps avoiding wasting effort on other simpler (but long) cases, only to discover that the proof can not be completed and all the work done has to be thrown away.

Assume we have these as the inference rules for the big step semantics. (If rules omitted)
$$
\begin{array}{c}
\dfrac{
}{\langle skip, \sigma \rangle \to_b \sigma}
\qquad
\dfrac{
\langle e, \sigma \rangle \to_e v
}{\langle x:=e, \sigma \rangle \to_b \sigma[x\mapsto v]}
\\
\dfrac{
\langle c_1, \sigma \rangle \to_b \sigma'
\qquad
\langle c_2, \sigma' \rangle \to_b \sigma''
}{\langle c_1;c_2, \sigma \rangle \to_b \sigma''}
\\
\dfrac{
\sigma\models \lnot\phi \quad
}{\langle while\ \phi\ do\ c, \sigma \rangle \to_b \sigma}
\qquad
\dfrac{
\sigma\models \phi \quad
\langle c, \sigma \rangle \to_b \sigma'
\quad
\langle while\ \phi\ do\ c, \sigma' \rangle \to_b \sigma''
}{\langle while\ \phi\ do\ c, \sigma \rangle \to_b \sigma''}
\end{array}
$$

We immediately get the following induction principle.

Let $p(c,\sigma,\sigma')$ be any property of a command and two states.
To prove that
$$
\forall c,\sigma,\sigma'.\ \langle c \sigma \rangle \to_b \sigma' \implies p(c,\sigma,\sigma')
$$
it suffices to check all of the following:

$\forall \sigma.\ p(skip,\sigma,\sigma)$
$\forall x,e,\sigma,v.\ \langle e, \sigma \rangle \to_e v \implies
p(x:=e, \sigma, \sigma[x\mapsto v])$
$\forall \sigma,\sigma',\sigma''.\
p(c_1, \sigma, \sigma') \land p(c_2, \sigma', \sigma'')
\implies p(c_1;c_2, \sigma, \sigma'')$
$\forall \phi,c,\sigma.\ \sigma\models \lnot\phi \implies
p(while\ \phi\ do\ c, \sigma, \sigma)$
$\forall c,\phi,\sigma,\sigma',\sigma''.\
\sigma\models \phi \land
p(c, \sigma, \sigma') \land
p(while\ \phi\ do\ c, \sigma', \sigma'') \implies
p(while\ \phi\ do\ c, \sigma, \sigma'')$

Note that in item 4 we get the induction hypotheses on the subterms, very much like what would happen using structural induction.

In step 5, instead, we get both an induction hypothesis on the subterm $c$, and (crucial!) another induction hypothesis on the $while$ itself (on different states).

For your case, choose a suitable property $p(c,\sigma,\sigma')$ such as "there is some natural $N$ for which $c,\sigma$ terminates in $N$ small steps in stale $\sigma'$".


When a trained RNN is tested, is the number of time-steps same for every input? I am a beginner in deep learning so bear with me. If I want to unfold the RNN in order to represent the relation of output to the input as a non-recursive functions I would have to know the number of time steps it takes for the RNN to make a prediction, correct? Hence it is important for me to know if the number of time steps is the same for every test input.

Will the number of time steps for an RNN which is unchanged in any way always stay the same?

When a trained RNN is tested, is the number of time-steps same for
  every input?

Typically, yes. If an input is too short, it can be padded. If an input is too long, it can encoded in some way to reduce length. A good discussion of these methods can be found here.

The reason I said typically is because an RNN is producing an output after each time step t. That is for each time step t there is an input t and output t. In classification tasks, we usually only want the last output. But in generative tasks we would want the output at each time t. It is certainly possible for the length to differ between inputs.

So like most things in machine learning the answer is, it depends.


How can it be decidable whether $\pi$ has some sequence of digits? We were given the following exercise.

  Let

  $\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$

  Prove that $f$ is computable.

How is this possible? As far as I know, we do not know wether $\pi$ contains every sequence of digits (or which) and an algorithm can certainly not decide that some sequence is not occurring. Therefore I think $f$ is not computable, because the underlying problem is only semi-decidable.

There are only two possibilities to consider.

For every positive integer $n$, the string $0^n$ appears in the decimal representation of $\pi$.  In this case, the algorithm that always returns 1 is always correct.
There is a largest integer $N$ such that $0^N$ appears in the decimal representation of $\pi$.  In this case the following algorithm (with the value $N$ hard-coded) is always correct:

Zeros-in-pi(n):
 if (n > N) then return 0 else return 1

We have no idea which of these possibilities is correct, or what value of $N$ is the right one in the second case.  Nevertheless, one of these algorithms is guaranteed to be correct.  Thus, there is an algorithm to decide whether a string of $n$ zeros appears in $\pi$; the problem is decidable.

Note the subtle difference with the following proof sketch proposed by gallais:

  Take a random Turing machine and a random input.
  Either the computation will go on for ever or it will stop at some point and there is a (constant) computable function describing each one of these behaviors.
  ???
  Profit!

Alex ten Brink explains:

  watch out what the Halting theorem states: it says that there exists no single program that can decide whether a given program halts. You can easily make two programs such that either one computes whether a given program halts: the first always says 'it halts', the second 'it doesn't halt' - one program is always right, we just can't compute which one of them is!

sepp2k adds:

  In the case of Alex's example neither of the algorithms will return the right result for all inputs. In the case of this question one of them will. You can claim that the problem is decidable because you know that there is an algorithm that produces the right result for all inputs. It doesn't matter whether you know which one that algorithm is.
  10


what is the Recent Nature Inspired Algorithm for Optimization? I'm into designing a recommender system for movie database and for effective optimization.I suggested the idea of using particle swamp optimization ,but my professors need recent algorithms,can any one suggest recent nature inspired algorithms for optimization.(After Cuckoo Search Optimization).

This paper[[1]] recommends the following Swarm Intelligence algorithms:

  Ant colony optimization
  Bat algorithm
  Cuckoo search
  Firefly algorithm
  Particle swarm optimization

[1]: "A Brief Review of Nature-Inspired Algorithms for Optimization"


Is there an NP-hard problem for which no Fixed-Parameter Tractable algorithm exists? Question
Is there an NP-hard problem for which we can add a parameter1 to create a "natural"2 parametrised problem for which no FPT algorithm exists?

The adding a parameter is needed because a NP-hard problem is normally just a question with a yes or no answer, if you want to limit some parameter you need to specify which one (even though something like $k$-Coloring might have an obvious one already), so with "specifying which parameter" one is limiting, one is "adding a parameter" to the problem. A more detailed description is included in the answer by Discrete Lizard.
I think Natural tries to exclude "trivial" parameterizations as I discuss in my first doubt in this question. Again a more detailed description is included in the answer by Discrete Lizard.

Doubt

It might be a trivial question as it perhaps is possible to always "stuff" the entire problem within the $f(k_1,k_2,..,k_m)$ part of the $f(k_1,k_2,..,k_m)n^c$ algorithm whilst setting $n=c'$ where $c'$ is an arbitrary constant. But perhaps the exact definition of FPT prevents such (ab)use of the concept of FPT.

Based on the comment of plop there indeed exists a trivial way to parameterize "any" (I assume any properly well-posed problem) problem, such that its parameterization is fpt. Those parameterizations use languages, which I assume to be what is described here. Such a "trivial" (in light of the question, not in light of difficulty) parameterization is intended to be ignored. So in the "words" of Discrete lizard: non-trivial parameter range(s) is(are) intended.

You have to be a bit careful with your question here. Note that an NP-hard problem is a decision problem, while FPT algorithms solve parametrized decision or search problems. So the question is a bit poorly formed. However, I think the question you probably intended to ask is:

Is there an NP-hard problem for which we can add a parameter1 to create a "natural"2 parametrised problem for which no FPT algorithm exists?

To which the answer is (unconditionally!) yes.
First of all, note that FPT, the class of problems that are solvable via a fixed parameter tractable algorithm, is a proper subset of XP, the class of "slice-wise polynomial" parameterized problems that can be solved by a polynomial-time algorithm if the parameter is fixed. In other words: $\mathrm{FPT} \subsetneq \mathrm{XP}$. (I must confess I'm not able to provide the proof by "standard diagonalization" which my source offers as the only justification. Perhaps a complexity theorist can help me out here)
Next, note that since at least one problem in XP cannot be solved by an FPT-algorithm, any XP-hard (in the sense of FPT-reductions) problem cannot be solved by an FPT-algorithm.
In the chapter "Provable Intractability: The Class XP" in Downey and Fellows' Fundamentals of Parameterized Complexity, they complete the argument by showing that what they call the PEBBLE GAME PROBLEM is XP-hard by "reinterpreting" a problem that is known to be at least PSPACE-hard (after "removing the parameter"), so certainly NP-hard. See there book chapter for more details.

Let me add that this result was very surprising to me as well, because for most practical problems, we require al sorts of conjectures ($P\neq NP$, ETH, SETH, 3-SUM, etc.), but this result is an actual fact that is independent of any conjecture.

1: To clarify, by "adding a parameter", I mean given an NP-hard problem $L\subseteq \Sigma^*$, define a parametrized problem $L'\subseteq \Sigma^* \times \mathbb{N}$ as $L':= \{\langle x, k\rangle \mid f(x)=k\}$ for some function $f : \Sigma^* \rightarrow \mathbb{N}$. This captures the intuitive idea that the additional parameter measures a property of the input.
2: The definition in 1 still allows all sorts of strange parameterizations with functions such as $f(x)\equiv 1$. Ideally, we'd require $f$ to measure something meaningful about the instance, but that seems hard to formalize. I couldn't think of any other formalisation that removes all "unnatural" parameterizations, either. So, I will instead copy the informal notion of "natural parameterized problems" from Downey and Fellows' book.


how to solve Hoare logic problems I'm having trouble proving Hoare logic questions as I'm not sure of the process that is taken to prove them. I understand that they're rules such as assignment axiom, pre-condition strengthening, post-condition weakening etc... but how you actually apply these rules to the question is a little out of my understanding.

Cheers

Here is the idea behind proving this triple. Let us denote by $s_0,i_0$ the values before the block, and by $s_1,i_1$ the values after the block. We are given that $s_0 = 2^{i_0}$, and furthermore it is clear that $i_1 = i_0 + 1$ and $s_1 = 2s_0$. But then
$$
s_1 = 2s_0 = 2\cdot 2^{i_0} = 2^{i_0+1} = 2^{i_1}.
$$
Whether this constitutes a proof of not depends on your normative environment.


LazyHeap data structure with $O(n)$ Insert, Delete, and Return operations Consider a data structure called LazyHeap that supports the following operations:

INSERT(x): Given an element $x$, insert it into the data structure. It has no cost.
DELETE(x): Delete $x$ from the data structure. It has no cost.
RETURN: Return an element $x$ such that its order, if the elements are sorted, satisfies:

$$k/2 - k/100 \le \mathrm{order}(x) \le k/2 + k/100\,,$$

where $k$ is the number of elements in the data structure (at the time RETURN is called). RETURN also has no cost.

Come up with a strategy for the comparisons so that the running time for any sequence of $n$ operations is less than $1000n$.

I know that sometimes you have to make comparisons between two elements so that you can perform RETURN operation correctly, where one comparison costs one unit. However, I'm not sure where to go from there. Any help would be appreciated!

I can't actually see an approach that would provide constant time insert and return of the mid-element in $O(1)$ (and I understand "no cost" to be some constant cost.) I have, however, some ideas that may suggest some solution.

One approach that comes to my mind are two heaps, one MIN and one MAX. The MIN heap would keep al elements greater than the current mid element (satisfying $\frac{k}{2} - \frac{k}{100} ≤ midElement ≤\frac{k}{2} + \frac{k}{100}$) and the MAX heap would store all smaller or equal ones. On INSERT(x) we'd need to keep the heaps as balanced as possible, so we would compare x with the current mid element, add it to the proper heap (MIN if x > midElement, else MAX) and if the difference between heaps' sizes would grow larger than 1, we'd take an element from the larger one and insert it to the smaller one. However, RETURN would work in $O(log(n))$, as after returning the top of one of the heaps we would need to repair that heap. INSERT would also take $O(log(n))$ and DELETE could be even linear (select the heap in $O(1)$, get to the proper level of it (elements on lower level are too too big/too small) and search the level in $O(n)$).

Another approach would be to keep a balanced tree (like RB-Tree or an AVL-Tree). The top element would always be the mid-element. However, here RETURN would also work in $O(log(n))$ because we'd need to reset the root after removing it. INSERT would also work in $O(log(n))$ for the insert itself + eventual balancing and so would DELETE.

Constant times required ("has no cost") brings Hash-tables to mind. Average INSERT would indeed take $O(1)$ and so would DELETE (if table size and hashing function would be properly designed). As for RETURN - one approach would be to track the inserted elements and keep the index of the current mid-element. If greater or smaller elements were inserted we'd consider selecting the "next mid-element", but this would probably require $O(n)$ time (or at least I can't see any other way doing it). So this would actually cause our RETURN to work in $O(1)$ (if we keep an index of the mid-element), but grow INSERT cost to $O(n)$ (and similarly for DELETE.)


P2P and C/S, is it possible to determine which one is more bandwidth consuming? In peer-to-peer (P2P) networks nodes are interconnected with each other. In client/server (C/S) networks clients talks to the server. If in a C/S network clients also want to talk with each other (such as in a multiplayer online game), then clients would have to communicate through the server.

Given these, is it possible determine which architecture is more bandwidth consuming?

One would say that P2P is better. But in reality, you cannot tell by the information you provided.

For instance, the bandwidth depends on queuing delays. Therefore, assume that one of the nodes in the P2P network has a very small queue (or overloaded), while our server is super powerful and its queue is hugly big ! Similarly, it depends on the latency of the nodes.

It depends on the bandwidth of the channels in the network.
It depends on the round trip time.  Therefore, P2P peers may be very far away from each other ! (China, Iran, Venzuela for example). etc ..


Formal language inverse How can you specify the "inverse" of a word, so:
let's say a word consists of a's and b's the language is:
$ww^{-1}$
the second word is the same as the first but every a is replaced by b and every b by a

What you're calling $w^{-1}$ is a special case of what's known as a homomorphism, where, informally speaking, we define a map $h$, from an alphabet $\Sigma$ to strings over an alphabet $\Gamma$ and then extend this in a natural way to maps of words. In your case, the map is particularly simple: $h(a)=b$ and $h(b)=a$. There's quite a bit known about such maps; for instance both regular and context-free languages are closed under homomorphisms.

(For what it's worth, your $ww^{-1}$ language isn't regular.)


Extended grammar form (backus-naur) and simple grammar forms equivalence Square braces around a grammar symbol or symbols denote that these constructs are optional. Thus, production A -> X[Y]Z has the same effect as the two productions A -> XYZ and A -> XZ.

Curly braces around a grammar symbol or symbols say that these symbols may be repeated any number of times, including zero times. Thus, A -> X{YZ} has the same effect as the infinite sequence of productions A -> X, A -> XYZ, A -> XYZYZ, and so on.

Show that these two extensions do not add power to grammars; that is, any language that can be generated by a grammar with these extensions can be generated by a grammar without the extensions.

Proof

A -> X[Y]Z     --->        A -> XZ | XYZ

A -> X{YZ}     --->        A -> XB
                           B -> YZB | ε

How can we prove that both forms will generate the same language?

Show that given a derivation in one grammar, there is a corresponding derivation in the other grammar which derives the same word. You might find it easier to work with parse trees instead of just derivations.

In the case of optional brackets, this is rather easy. Let us consider your example of a grammar with derivation rule $A \to X[Y]Z$ which is replaced by the derivation rules $A \to XZ$ and $A \to XYZ$. Given a derivation in the original grammar, each application of $A \to X[Y]Z$ replaces $A$ by $XZ$ of by $XYZ$. In the former case, we can simulate this in the new grammar using $A \to XZ$, and in the latter by $A \to XYZ$. Conversely, given a derivation in the new grammar, we can replace each application of the rules $A \to XZ$ and $A \to XYZ$ by an application of $A \to X[Y]Z$.

The case of braces is more complicated. One direction is easy – given a derivation in the original grammar, you can convert it to an equivalent derivation in the new grammar by replacing an application of $A \to X \{YZ\}$ by an equivalent derivation using only the rules $A \to XB$ and $B \to YZB \mid \epsilon$. In the other direction, you have to first show that if $B$ appears in a parse tree, then you can associate with it a path in the tree which corresponds to a derivation of the form $B \to YZB \to (YZ)^2B \to \cdots \to (YZ)^k$ for some $k \geq 0$. Given that, every application of $A \to XB$ can be associated with a path corresponding to a derivation $A \to^* X(YZ)^k$, which can be implemented in the old grammar by the rule $A \to X \{YZ\}$.

In the last paragraph I have been vague about some association of vertices in the parse tree to a path and to a derivation, which really amounts do a decomposition of all legal parse trees. These concepts will have to be formalized in a formal proof of equivalence.


Expected number of coins Alice and bob play a game.
Bob has a well-shuffled deck of $M=4999$ white cards and $N=4999$  green cards. Each permutation of cards in the deck is equally likely. Alice has set some rules for Bob.

Every time Bob flips a white card he gets one coin, otherwise he loses one coin. At any moment (even at the beginning), Bob is allowed to stop playing the game and keep the number of coins that he has.
During the game-play the balance of coins that Bob has may be negative.

If Bob plays optimally, what the expected amount of coins Bob will have?

Can any body give me an idea or a hint how to solve it.

Let $w(a,b)$ be the expected profit with $a$ positive cards and $b$ negative cards. Then $w(0,0) = 0$ and
$$
w(a,b) = \max\bigl(0, \tfrac{a}{a+b} (w(a-1,b) + 1) + \tfrac{b}{a+b} (w(a,b-1) - 1)\bigr).
$$
Indeed, if we stop the game immediately, the profit is zero. Otherwise, with probability $\tfrac{a}{a+b}$, we pull out a positive card, and with probability $\tfrac{b}{a+b}$, we pull out a negative card.

Using this recurrence, it is easy to compute $w(4999,4999)$. On my laptop it took less than a second.


How to fool the plot inspection heuristic? Over here, Dave Clarke proposed that in order to compare asymptotic growth you should plot the functions at hand. As a theoretically inclined computer scientist, I call(ed) this vodoo as a plot is never proof. On second thought, I have to agree that this is a very useful approach that is even sometimes underused; a plot is an efficient way to get first ideas, and sometimes that is all you need.

When teaching TCS, there is always the student who asks: "What do I need formal proof for if I can just do X which always works?" It is up to his teacher(s) to point out and illustrate the fallacy. There is a brilliant set of examples of apparent patterns that eventually fail over at math.SE, but those are fairly mathematical scenarios.

So, how do you fool the plot inspection heuristic? There are some cases where differences are hard to tell appart, e.g.

[source]

Make a guess, and then check the source for the real functions. But those are not as spectacular as I would hope for, in particular because the real relations are easy to spot from the functions alone, even for a beginner.

Are there examples of (relative) asymptotic growth where the truth is not obvious from the function definiton and plot inspection for reasonably large $n$ gives you a completely wrong idea? Mathematical functions and real data sets (e.g. runtime of a specific algorithm) are both welcome; please refrain from piecewise defined functions, though.

Speaking from experience, when trying to figure out the growth rate for some observed function (say, Markov chain mixing time or algorithm running time), it is very difficult to tell factors of $(\log n)^a$ from $n^b$. For example, $O(\sqrt{n} \log n)$ looks a lot like $O(n^{0.6})$:

[source]

For example, in "Some unexpected expected behavior results for bin packing" by Bentley et al., the growth rate of empty space for the Best Fit and First Fit bin packing algorithms when packing items uniform on $[0,1]$ was estimated empirically as $n^{0.6}$ and $n^{0.7}$, respectively. The correct expressions are $n^{1/2}\log^{3/4}n$ and $n^{2/3}$.


Does this loop invariant guarantee that the variable never changes? Suppose you have some loop and and integer k:

int k = 5;
for (int i = 0 ; i < N; i++)
{
  //(*)
  //do something
}

The loop invariant at (*) is:
$\{ K=k\}$

Does that guarantee that $k$ doesn't change in between iterations? if not, is there any otherway to guarantee that?

The loop invariant doesn't "guarantee" anything. It is a summary of relevant information you know about the state of the program when it reaches that point. If your loop is e.g.:

k = 5;
...
for(int i = 0; i < N; i++) {
   /* Invariant: k = 5 */
   ...
   k = 207;
   ...
   frob_very_hard(&k);
   ...
   k *= 3;
   ...
   k = 5;
}

at the marked point k == 5, but not all over the program.


Is FACTORIZATION or PRIMES known to be in LOGSPACE Are the integer factorization and PRIMES known to be in LOGSPACE?

Recently, it has been shown by researchers that PRIMES is in P. But this does not say anything about LOGSPACE since it is not known if LOGSPACE = P.

Factoring is not known to be even in $\mathsf{P}$.

Primality is not known to be in any class conjectured to be smaller than $\mathsf{P}$ (AFAIK).


Using Chebyshev to derive an upper bound for Coupon Collecter's Problem I'm TA'ing a course and have trouble solving an exercise.

Let $X$ be a RV defined to be the number of trials required to collect at least one of each type of coupon (of which there are $n$). Then $E[X] = nH_n = n \ln(n) + O(n)$ and $\sigma^2_X = n^2 \sum_{i=1}^n \frac{1}{i^2} - nH_n$ with $\lim_{n \to \infty} \frac{\sigma^2_X}{n^2} = \frac{\pi^2}{6}$. The exercise asks how Chebyshev's inequality can be used to upper bound the probability that $X > \beta n \ln(n)$ for some $\beta > 1$.

I tried this:
\begin{align*}
Pr[X>\beta n \ln(n)] &\leq Pr[|X-\mu_X| \geq (\beta - 1)n \ln n] \\
&\leq Pr\left[|X-\mu_X| \geq (\beta - 1) \left( \frac{\sqrt 6}{\pi} \sigma_X \right) \ln n\right] (1) \\
&\leq \frac{\pi}{6(\beta -1)^2 \ln^2 n} = O\left(\frac{1}{\ln^2n}\right)
\end{align*}

where (1) follows because $n > \frac{\sigma_X \sqrt 6}{\pi}$. However I believe the first inequality is incorrect because I'm discarding the $-  O(n)$ from $\mu_X$ in deriving an upper bound.

I also tried something else:
\begin{align*}
Pr[X>\beta n \ln(n)] &\leq Pr[|X-\mu_X| \geq \beta n \ln n - nH_n] \\
&\leq Pr[|X-\mu_X| \geq (\beta -1)nH_n] \\
&= Pr\left[|X-\mu_X| \geq \frac{6(\beta - 1)H_n}{\pi^2n} \left(n^2 \sum_{i=1}^\infty \frac{1}{i^2} - n H_n \right)\right]
\end{align*}

but I'm not sure where to go from here. Thanks for any help!

As you should have suspected, there is only a thin line between what you have tried and what is rigorous.

Here it is the rigorous version of your attempt. Since $\beta n\ln n\gt \mu_X$ when $n$ is large enough, the first inequality holds for $n$ large enough.
\begin{align*}
Pr[X>\beta n \ln(n)]
&\leq Pr[|X-\mu_X| \geq \beta n \ln n - \mu_X] \\
&\le \frac{\sigma_X^2}{(\beta n \ln n - \mu_X)^2}.\\
\end{align*}
Now

$$\begin{aligned}
\lim_{n\to\infty}\frac{\frac{\sigma_X^2}{(\beta n \ln n - \mu_X)^2}}{\frac1{\ln^2 n}}
&=\lim_{n\to\infty}{\frac{\sigma_X^2}{n^2}}\lim_{n\to\infty}\frac{(n\ln n)^2}{(\beta n \ln n - \mu_X)^2}\\
&=\frac{\pi^2}{6}\lim_{n\to\infty}\frac{1}{(\beta - \frac{\mu_X}{n\ln n})^2}\\
&=\frac{\pi^2}{6(\beta - 1)^2},
\end{aligned}$$
which implies $$\frac{\sigma_X^2}{(\beta n \ln n - \mu_X)^2} = O\left(\frac{1}{\ln^2n}\right).$$


Tolerated use of the term topology In the field of data structures (and maybe in graph theory), can we use the term topology to speak about the shape of a tree? For instance, consider the two following trees :

1) The first one:
Node $a$ is parent of $b$ and $c$.
Node $e$ is parent of $a$ and $d$

2) the second one:
Node $a$ is parent of nodes $b$, $c$ and $d$.

Can we say that their topology are different, in the sense that the set of relations parents/children are different?

Yes, I suppose you could, though it might be viewed as a somewhat informal usage of the term "topology".  "Shape" would probably be a better word, as @Raphael suggests.

A more precise way would be to say that these two trees are not isomorphic.

Background: Two graphs $G,G'$ are considered isomorphic if there exists a map $f:V \to V'$ that is a graph isomorphism.  Since any tree can be viewed as a graph, you can consider two trees to be isomorphic if they are isomorphic as graphs.  One can also define a natural notion of a tree isomorphism directly; this happens to be equivalent to the notion of a graph isomorphism for unrooted trees, but is slightly different (and more appropriate to use) for rooted trees.  You can read more about isomorphisms in standard sources.


Shunting-yard algorithm - proof How can one prove that a shunting-yard algorithm always returns a correct expression in RPN? I cannot find any proof in the internet.

The shunting-yard algorithm was introduced in Dijkstra's article Making a Translator for ALGOL-60 (APIC Bulletin no7, 1961; see this PDF, from p.22; also published in Annual Review in Automatic Programming, 7:3–11, 1963 and available from Science Direct if your institution has a subscription).  Pages 7–9 of the article (pp.28–30 of the PDF) explain how the algorithm works and argue its correctness. It's not a formal proof but it looks like it contains everything you should need to produce one.


How does Logical Block Addressing affect OS disk scheduling optimizations such as SCAN (Elevator Algorithm)? If the OS is scanning from one edge of the disk to the other, doing so from behind the Logical Block Addressing (LBA) abstraction, although it may aim to service requests in an elevator-like way, what guarantee do we have that the physical mapping correlates to what we see as the OS?

i.e. Could it be that servicing requests in logical order would end up seeking to random physical sectors, or do logical addresses still approximately reflect physical locations?

You are right, this could be a problem.

In older disks, the physical block number corresponds to the actual location of the block on the disk.  So, that algorithm makes sense.

Newer disks do fancier stuff.  They have firmware that might remap blocks around to different locations, so that the physical block number no longer corresponds to the actual location of the block on disk in all cases (two blocks with similar physical block number might be far apart in actuality).  Because this can screw up OS scheduling algorithms, disk firmware generally tries to avoid this situation where possible, but it can happen.

It gets especially tricky with SSDs, which have very different performance properties than hard disks, but which must (for backwards compatibility) use an API originally designed for magnetic disks.  So, modern SSD's do clever things to try to ensure that typical OS scheduling algorithms will still yield reasonable results, even though the physical block number doesn't necessarily correspond to the actual physical location of where the data is stored on the SSD.


Is this an LL(1) grammar? How to solve First - Follow conflict? im trying to check if this grammar is LL(1).

S -> L = R
L -> * L | id
R -> L | R + R | num

As you can see there is a Left recursion on R production. So i remove that and what i get is:

S -> L = R
L -> * L | id
R -> L R' | num R'
R' -> + R R' | ε

Now the problem that i have is that First and Follow set of R' rule have a common non-terminal ("+") and also FIRST(R) and FOLLOW(R') has a common non-terminal.
So i wonder how to create the parsing table if there's this conflict. My question is: is there a way to solve this problem or simply this isn't an LL(1) grammar?

Thanks.

Your factoring is wrong. It should be (written as regular espressions):

$\begin{align*}
  R
    &\to (L \mid \operatorname{num}) (+ R)^*
\end{align*}$

Thus the grammar with left recursion fixed is:

$\begin{align*}
   S  &\to L = R \\
   L  &\to * L \mid \operatorname{id} \\
   R  &\to L R' \mid \operatorname{num} R' \\
   R' &\to + R R' \mid \varepsilon
\end{align*}$

You can check that this doesn't have conflicts.


How to resolve a recurrence relation in the form of $T(n) = T(f(n))*T(g(n)) + h(n)$ I am basically trying to solve the following question:

Given a set $P = \{\{1\},\{2\},\dots,\{n\}\}$ of $n$ sets of elements, our aim is to merge these elements into one set.

At each step, sets can be only merged pairwise.

How many different ways can this merge happen?

For instance, given $P = \{\{a\},\{b\},\{c\},\{d\}\}$:

After the first step we can end up with three different combinations:
\begin{array}{c}
P_{11} = \{\{a,b\}, \{c,d\}\}\\
P_{12} = \{\{a,c\}, \{b,d\}\}\\
P_{13} = \{\{a,d\}, \{b,c\}\}\\
\end{array}

And all the sets will be merged after the second step:
\begin{array}{c}
P_{2} = \{\{a,b,c,d\}\}\\
\end{array}
All the examples I could find about recurrences is summation of two recurring functions such as

$T(n) = T(n) + T(n/2) + \Theta(n)$

However, I want to solve a recurrence relation where recurring function is multiplied by itself:

$T(n) = T(n^2-n)*T(n/2)$

I am not sure that I write the recursion correct but this is what I want:

\begin{array}{l}
n\\
\dfrac{n(n-1)}{2}*\dfrac{n}{2}\\
\dfrac{n(n-1)}{2}*\dfrac{n}{2}*\dfrac{\frac{n}{2}\left(\frac{n}{2}-1\right)}{2}*\dfrac{n}{4}\\
\end{array}

At first sight, the number of nodes in the recursion tree grows like $O(n) \rightarrow O(n^3) \rightarrow O(n^6) \dots$ at each level, which can be formulated as $n^{2k}$.

Since the size of the problem is reduced by a factor of 2, we have $\log n$ depth in the recursion tree. Therefore, $n^{2k} = \log n$ and $2k = \log_{n}\log n$ which does not seem a reasonable size.

Where am I mistaken?

If you have a recurrence involving only multiplication, take the logarithm:
$$
\log T(n) = \log T(n^2-n) + \log T(n/2).
$$
This converts it into an additive recursion. In your case this is not really a recursion since it defines $T(n^2-n)$ in terms of $T(m)$ for $m < n^2-n$, but not every integer is of the form $n^2-n$.

Regarding your original question, try to relate it somehow to binary trees, which are known to be counted by the Catalan numbers.


1's complement addition of outer carry to the result Let's take for example this addition: 3 + (-1).

1 in binary is 001, and to obtain it's 1's complement counterpart we
flip the bits. So it is: 110.

3 in binary is 011.

011 + 110 = 1001
That first 1 which is in bold has to be added to the number formed by the last 3 bits as follows:
001 + 1 = 010 (2 in decimal).

Why do we do the last step, adding that outer carry? Which is the logic behind?

I only understand two's complement

Let's take two 3 bits numbers, X and Y

Complementing the bits is like calculating 111-X

(it is obvious as $\overline {b} = 1-b$, $\sum_{i=0}^n 2^i*(1-b_i) = \sum_{i=0}^n 2^i -  \sum_{i=0}^n 2^i*b_i$...)

The addition becomes 111-X+Y

If you add 1 you get 1000-X+Y. The leftmost carry is discarded.


Why polynomial time is called "efficient"? Why in computer science any complexity which is at most polynomial is considered efficient?

For any practical application(a), algorithms with complexity $n^{\log n}$ are way faster than algorithms that run in time, say, $n^{80}$, but the first is considered inefficient while the latter is efficient. Where's the logic?!

(a) Assume, for instance, the number of atoms in the universe is approximately $10^{80}$.

Another perspective on "efficiency" is that polynomial time allows us to define a notion of "efficiency" that doesn't depend on machine models. Specifically, there's a variant of the Church-Turing thesis called the "effective Church-Turing Thesis" that says that any problem that runs in polynomial time on on kind of machine model will also run in polynomial time on another equally powerful machine model.

This is a weaker statement to the general C-T thesis, and is 'sort of' violated by both randomized algorithms and quantum algorithms, but has not been violated in the sense of being able to solve an NP-hard problem in poly-time by changing the machine model.

This is ultimately the reason why polynomial time is a popular notion in theoryCS. However, most people realize that this does not reflect "practical efficiency". For more on this, Dick Lipton's post on 'galactic algorithms' is a great read.


How many words of memory map to the same cache entry? I am going over some practice questions for the Major field exam and it asks:

A processor with a word-addressable memory has a two-way set-associative cache. A cache line is one word, so a cache entry contains a set of two words. If there are  M  words of memory and C cache entries, how many words of memory map to the same cache entry?

I am not sure how to even approach this problem since I am not too familiar with computer organization. Any help would be appreciated. Thanks!

The correct answer is M/C. This question is on the Computer science Major Field Assessment Test. https://www.ets.org/Media/Tests/MFT/pdf/mft_samp_questions_compsci.pdf


Lambda Calculus Conversion How can I take a Haskell data type or function (eg fold, list, String, zip) and convert or translate it to a lambda calculus abstraction?
Example:
If sum computes a sum of all elements in a list, and
:type sum = Num a => [a] -> a.
    sum []     = 0
    sum (x:xs) = x + sum xs

How do I take this information to translate it to a lambda calculus expression, or rather an abstraction?
I have tried to find guides online but they just give me the answers. I want to know how to actually make the conversion/translation from a Haskell function like add, sum, map, fold, etc. to a lambda calculus abstraction.

The thing to notice here is that your function sum is defined on lists, which are inductively defined. Theoretically, the inductive definition of a list defines for every type T a term
match_list :: T -> (a -> [a] -> T) -> ([a] -> T)

satisfying the property
match_list s t [] = s
match_list s t (x::xs) = (t x xs)

in addition, defining a recursive function requires an untypable fixed-point combinator fix satisfying the property
fix F = F (fix F)

so combining the two, we could write your definition by first defining
F :: ([a] -> a) -> ([a] -> a)
F := λ f -> match_list 0 (λ x -> (λ xs -> x + f xs))

and then
sum := λ x -> (fix F) x
     = λ x -> (fix (λ f -> match_list 0 (λ x -> (λ xs -> x + f xs)))) x

To convince oneself that this works, let's try this on the example
sum [1,2] = (fix F) [1,2]
          = (F (fix F)) [1,2]
          = (λ f -> match_list 0 (λ x -> (λ xs -> x + f xs))) (fix F) [1,2]
          = match_list 0 (λ x -> (λ xs -> x + ((fix F) xs))) [1,2]
          = 2 + ((fix F) [1])
          = 2 + ((F (fix F)) [1])
          = 2 + ((λ f -> match_list 0 (λ x -> (λ xs -> x + f xs))) (fix F) [1])
          = 2 + (match_list 0 (λ x -> (λ xs -> x + ((fix F) xs))) [1])
          = 2 + (1 + ((fix F) []))
          = 2 + 1 + ((F (fix F)) [])
          = 2 + 1 + ((λ f -> match_list 0 (λ x -> (λ xs -> x + f xs))) (fix F) [])
          = 2 + 1 + (match_list 0 (λ x -> (λ xs -> x + (fix F) xs)) [])
          = 2 + 1 + 0

This is theoretically what would go on in a purely functional language (for example the untyped lambda calculus), however in languages like haskell, lisp, or ocaml (I am unaware of inductive datatypes in python), the terms match_list and fix are "internal" constructs and are not explicit terms in the language.


Is the verifier for an $NP$ and its $co-NP$ the same? I have a hard time to find the goal of having $co-NP$ problems.

$NP$: Is there a Hamiltonian path in this graph?

We need to bring a certificate, and the verifier checks the certificate in polynomial time. However, finding such a path might not be done in polynomial time. It may need searching the entire problem space.

$co-NP:$ Isn't there any Hamiltonian path in this graph?

To say "no", we need to bring a counterexample, and the counterexample (the same certificate) is checked by [the same] verifier in polynomial time. However, finding such a counterexample might not be done in polynomial time.  It may need searching the entire problem space.

Am I right in the definition of my examples?

It seems we can reduce them to each other:

For example, "Isn't there any Hamiltonian path in this graph?" We ask the complement $NP$ problem "Is there any Hamiltonian path in this graph", if it said "Yes", we would say "No" to the $co-NP$ problem and if it said "No", we would say "yes" to the $co-NP$ problem.

So, what is actually the difference? Is it just playing on words? Are there questions for which the NP and its co-NP different to answer?

Anyway, I don't know the goal here, please guide me.

I think you might be slightly confusing your definition for co$NP$. To show that a certain graph doesn't contain a Hamiltonian path, you need to show that all paths in it aren't Hamiltonian, and providing a specific path as a "counter example" isn't enough.

In general, $coNP$ isn't defined using a witness the same way $NP$ is, because if it did than it would be the same as $NP$, and for now this is an open problem (we don't know if the two are equal, and they are usually believed to be different). Therefore, it doesn't really make sense to talk about a witness for a $coNP$ problem the same way you talk about a witness for an $NP$ problem.

Specifically, for a certain language in $coNP$ and a witness-based TM $M$ accepting it, $x$ is in the language iff $M$ accepts $(x,v)$ for all witnesses $v$. This is in contrast to a TM for a language in $NP$ that needs to accept only for a single witness.

I would like to add that for me, studying about the Polynomial Hierarchy using its witness-related definitions helped me understand $coNP$ better, but it isn't a necessity.


Is it true that for every genetic algorithm there exists a non-genetic algorithm that achieves the same results more efficiently? And if it is not true, what are the problem classes or characteristics for which genetic algorithms are superior?

What you might have heard could have been a formulation of a No Free Lunch Theorem. Loosely, those results say that you can either have an optimization algorithm that does fairly well on many problems, or really well on some problems, but not both.

Genetic Algorithms are rather broad classes of optimizers, so you can typically apply them to many types of problems with decent results, but for specific problems there will typically be more efficient algorithms that only work for this type of problem.


Where's the flaw in my algorithm? (Linear program to solve NP-hard problem) The problem (copy-pasted from this question on cs.stackexchange):

Given a connected, directed graph $G=(V,E)$, vertices $s,t \in V$ and a coloring, s.t. $s$ and $t$ are black and all other vertices are either red or blue, is it possible to find a simple path from $s$ to $t$ with more red than blue vertices in polynomial time?

My algorithm:
We first add weights to the edges:

If the edge goes into a red vertex, we let its weight be -1.
If the edge goes into a blue vertex, we let its weight be 1.
Any edge going into $t$ has weight 0.

This way, any path from $s$ to $t$ with negative weight is a solution.

We now formulate a linear program, which finds the path with lowest weight from all paths with length $\le c$ (i.e. it only looks at paths with $\le c$ edges ):

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

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

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

This linear program is, except for the constraint $\sum_{e\in E} x_e \le c$, identical to the one which I asked about in my previous question, and in which it is proved that that linear program indeed returns a shortest path.

Even with the newly added constraint $\sum_{e\in E} x_e \le c$ to me it looks like my previous reasoning is still valid.

If that were the case however, we could solve the linear program for $c=1,...,|E|$, and for each solution check whether its weight is negative. If we find any solution for which the weight is negative, we have a path as is requested by the problem.

If all solutions have positive weight, then there is no such path.

As each LP-program runs in polynomial time, and we have to run $|E|$ variations of this program, the whole algorithm should still be run in polynomial time.

This however clashes with the fact that the problem itself is NP-hard.

So, somewhere in my reasoning is a mistake (most likely the result of the linear program doesn't have to be a path anymore or something similar) - however, I simply can't find what exactly is going wrong. Where is it?

Edit:

The reasoning (copied from the previous question) for the correctness of the linear program:

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

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

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

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

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

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

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

In your program specification, "$\forall e\in E: x_e \ge 0$" should be "$\forall e\in E: x_e=0\text{ or } 1$".

"Each LP-program runs in polynomial time". However, your instance is an instance of integer linear programming (ILP), which is NP-hard, even when all variables are restricted to be either 0 or 1. In particular, this answer shows that the instances of ILP as given in this question is NP-complete.


Show that CFG is not a LR(1) Grammar Let G b the following CFG (Where S is the start symbol):

S→aB|aDc
B→bBc|c
D→bc|c

(a) Show that G is ambiguous.
(b) Show that G is not an LR(1) grammar.
(c) Modify G into an equivalent grammar G′ that is LR(1). Explain why G′ is an LR(1) grammar and why G and G′ are equivalent.

My current answers:

(a) I showed that there exists two left derivation trees for string abcc - therefore it is ambiguous.

(b) I simply stated that an LR(1) grammar is not ambiguous by definition, and since (a) shows it is ambigious it follows that G is not an LR(1) grammar.

(c)
G':

S→aB
B→bBc|c

I removed the nonterminal D, which makes it unambiguous.

Questions:

Is there a more suiting answer for (b)?

How do I explain why G' is an LR(1) grammar in (c)?

Thank you!

Your answer to B is perfectly fine.

To show that something is LR(1) you should generate the automaton and show it has no conflicts.

Don't forget you have to show that G and G' generate the same language. Luckily this is simple because your removal of rules only involved a finite sub language thus you can exhaustively show equivalence.


Pipelining and instruction cycle Consider the sequence of machine instruction given below:
\begin{array}{ll} \text{MUL} & \text{R5, R0, R1} \\  \text{DIV} & \text{R6, R2, R3} \\   \text{ADD} & \text{R7, R5, R6} \\  \text{SUB} & \text{R8, R7, R4}  \\ \end{array}
In  the above sequence, $R0$ to $R8$ are general purpose registers. In the instructions shown, the first register shows the result of the operation performed on the second and the third registers. This sequence of instructions is to be executed in a pipelined instruction processor with the following $4$ stages: $(1)$ Instruction Fetch and Decode $(IF)$, $(2)$ Operand Fetch $(OF)$, $(3)$ Perform Operation $(PO)$ and $(4)$ Write back the result $(WB)$. The $IF, OF$ and $WB$ stages take $1$ clock cycle each for any instruction. The $PO$ stage takes $1$ clock cycle for $ADD$ and $SUB$ instruction, $3$ clock cycles for $MUL$ instruction and $5$ clock cycles for $DIV$ instruction. The pipelined processor uses operand forwarding from the $PO$ stage to the $OF$ stage. The number of clock cycles taken for the execution of the above sequence of instruction is _________.
I got the answer as 15 however the correct answer is 13. Am I doing something wrong or is the answer key at fault?
The link for reference: https://gateoverflow.in/8218/gate2015-2-44

Note the sentence "The pipelined processor uses operand forwarding from the PO stage to the OF stage". That means if a result is written at cycle n, the same result can be read as an operand at the same cycle n. This happens twice in your instruction sequence. If you ignore this, your count will be too high by two.


Interval scheduling scheduling problem with minimal workers I am writing a greedy algorithm for a variation of the interval scheduling problem that I haven't seen before.

I have a set of jobs, each with start and finish time. All jobs in set must be assigned to a worker, workers cannot have overlapping jobs. My greedy algorithm should minimise workers - use the least number of workers possible to complete all jobs.

Does this algorithm accomplish this? It seems too simple to me and I have probably neglected to think of something.

sort(jobs) //earliest starting time first

w = 0 //number of allocated workers

for i = 1 to n {
    if (worker w has no job with finish time later than starting time of job i)
        schedule(worker w, job i)
    else
        schedule(worker w+1, job i)
        w++

This is called Interval Partitioning Problem or Interval Coloring Problem in this lecture note, as well as in Section 4.1 of the book [1].

  Given intervals $(s_i, f_i)$, assign them to processors/workers so that you
  schedule every interval and use the smallest number of processors/workers.

The greedy algorithm is a simple one-pass strategy that orders intervals by their starting times, goes through the intervals in this order, and tries to assign to each interval it encounters a processor/worker that has not already been assigned to any previous interval that overlaps it.

[1] Algorithm Design. By Jon Kleinberg and Eva Tardos.


What does the complexity class $\mathsf{XP}$ stand for? $\mathsf{XP}$ is the class of problems with input length $n$ and parameter $k$ than can be solved in $O(n^{f(k)})$ time, where $f$ is a computable function. It's described on the complexity zoo page as "Fixed-parameter Tractable for Each Parameter", but I fail to see how adding "for each parameter" to the description causes such a significant change to the definition compared to $\mathsf{FPT}$, which contains problems solvable in $O(f(k)\cdot n^{O(1)})$ time.

The complexity zoo page mentions the book it was defined in, Parameterized Complexity, but I don't have access to it right now.

There is a slightly different description for XP which I personally find less misleading: "Polynomial time for each parameter". I believe the zoo page uses FPT instead of P for some formal reasons (parameterized problems are sometimes defined as subsets of $\Sigma^*\times\Pi^*$, classical problems as subsets of $\Sigma^*$). It can be noted that both formulations describe non-uniform XP, while the time bound $O(n^{f(k)})$ refers to uniform XP. In any case, the important difference is that for XP, the exponent of $n$ may depend on the parameter, for FPT it mustn't.

The practical importance of XP is as a door to parameterized complexity analysis. Once a problem is recognized as belonging to XP it makes sense to investigate its exact parameterized complexity. If it does not even belong to XP, parameterized analysis doesn't make much sense. It can also be argued that in that case the parameterization is not meaningful.


Selection Sort runtime in terms of Big O I'm trying to understand why the sorting algorithm Selection Sort has asymptotic runtime in $O(n^2)$.

Looking at the math, the runtime is

$\qquad T(n) = (n-1) + (n-2) + \dots + 2 + 1$.

And this is stated to be equal to

$\qquad O(n^2)$.

However I just don't understand the intuition. I have tried several practical experiments for n=10 up to n=5000, and all point to that the time complexity of e.g. 5000 can never be greater T(5000) = 12.497.500 -- not T(5000) = 5000^2 = 25.000.000.

Now, I know that 5000 is not the same as infinity, but I just don't understand the intuition behind

$\qquad (n-1) + (n-2) + \dots + 2 + 1 = O(n^2)$.

Does someone have a great pedagogical explanation that my dim-witted mind can understand?

Remember what $O(n^2)$ means: it means that there is a constant $c$ such that, for large enough $n$, the number of steps is at most $cn^2$.  The constant doesn't have to be $1$; in this case, it looks like the constant is about $\tfrac12$.

Why is $(n-1) + (n-2) + \dots + 2+1$ equal to $O(n^2)$?  Because you're adding up $n-1$ numbers and the average of those numbers is half-way between the first one and the last one, i.e., $\tfrac12(1 + (n-1))$.  So the total is $$(n-1)\times \tfrac12(1 + (n-1)) = \tfrac12(n^2-n).$$Plug in $n=5000$ and you get... *drumroll*... $12497500$.


Probabilities of duplicate mail detection by comparing notes among servers I have the following problem:

We want to implement a filtering strategy in e-mail servers to reduce the number of spam messages. Each server will have a buffer, and before sending an e-mail, it checks whether there is a duplicate of the same message in its own buffer and contacts k distinct neighboring servers at random to check whether the duplicate is in another buffer. In case any duplicate message is detected, it will be deleted as spam, otherwise it will be sent after all negative replies are received.
Let us assume that there are N mail servers, and that a spammer sends M copies of each spam mail. We assume that all copies are sent simultaneously and that each mail is routed to a mail server randomly.

Given M, N and k I need to find out the probabilities that no spam message is deleted (i.e. no server detects spam), all spam messages are deleted (all servers detect spam) and spam messages are deleted from at at least one server.
So far, I have used combinations without repetition to find out the cases that need to be taken into account for an M and N. Now I need to find out the probability that one server receives at least two copies of a message, but I am at complete loss. Could you please provide some insight into the problem?

If a given server receives $m \leq M$ copies, it does not receive $M-m$ copies. Also, there are many ways to pick $m$ messages out of $M$; you have to consider all of them. Furthermore, important assumptions are that

"randomly" means "uniformly at random", that is the probability that any given copy goes to any given server is $\frac{1}{N}$, and that
each copy is routed independently of its siblings, that is we have independent random events for the individual copies.

This is all you need to piece together the probability $\operatorname{Pr}(S_i = m)$ that server $i$ receives $m$ messages.

   If you put the above together, you get

 $\qquad \displaystyle \operatorname{Pr}(S_i = m) = \binom{M}{m} \left(\frac{1}{N}\right)^m \left(1 - \frac{1}{N}\right)^{M-m}$

 for $S_i$ being the number of copies the $i$-th server receives, $1\leq i \leq N$. You should recognize this kind of probability weight.

 If you have doubts that this is correct, run some simulations (not a proof!).

Now it is easy to compute $\operatorname{Pr}(S_i \geq 2) = 1 - \operatorname{Pr}(S_i = 1) - \operatorname{Pr}(S_i = 0)$.

   When using the derived weight in other calcuations, keep in mind that the $S_i$ are not independent because $\sum_{i=1}^N S_i = M$. The underlying probability distribution is the well-studied multinomial distribution.


Is this a syntax error or a semantic error? I came across the following question

The error in the expression " if x>y x=2; " is detected by
a. Syntax analyzer
b. Lexical analyzer
c. semantic analyzer

I know that the parentheses of x>y are missing, but it is not syntax error right? as all the syntaxes are correct, but we are missing a pair of parenthesis.. so is this a semantic error?
The correct answer is given as a.

The classification as lexical/syntax/semantic error is largely artificial, governed by separate parts of your compiler: it the "lexical analysis" phase detects the error, it is deemed lexical; if the parsing (syntax analysis) phase does, it is classified as "syntax error", others are reported as "semantic errors" (or just pass through without detection, giving rise to a runtime error). This is more am implementation detail than a firm distinction. It is e.g. possible to do away with separate lexical analysis and do all as parsing, some "syntax errors" aren't really parsing errors, but undefined variables, some semantic problems can be detected when parsing. Some languages (infamously C++) are complex enough that checking syntax requires checking much beyond context free grammar aspects to catch "syntax errors".


How to reduce INDEPENDENT SET to INDEPENDENT SET SIZE? Suppose you are given a polynomial-time algorithm for the following problem related to INDEPENDENT SET:

INDEPENDENT SET VALUE

Input: An undirected graph G.

Output:The size of the largest independent set in G (but not the set itself).

Show how you can use this algorithm to solve the INDEPENDENT SET problem in polynomial time: given a graph G, return an independent set which is as large as possible.

Any help would be really appreciated. I am pretty lost in this question

There's a couple of issues to address, first is what definition of INDEPENDENT SET you are using, the "standard" definition is

INDEPENDENT SET (Decision)
Input: A graph $G$ and a number $k \in \mathbb{N}$.
Question: Does $G$ have an independent set of size at least $k$?

This is the decision version of the problem, and it should be pretty obvious how to use INDEPENDENT SET VALUE to solve it.
If you however mean the search (or optimization) version of the problem:

INDEPENDENT SET (Search / almost Optimization)
Input: A graph $G$ and a number $k \in \mathbb{N}$.
Output: An independent set $I\subseteq V$ where $|I| \geq k$.

If we're looking at the optimization version, then we have the optimization criterion "maximise $k$".
In these cases we can still use INDEPENDENT SET VALUE to solve the problem in polynomial time. What we want is an algorithm that makes a polynomial number of calls to our INDEPENDENT SET VALUE sub-routine, and at each step decides what to do with some element of the graph.
Further hints in spoilers (don't cheat! ;) ):

 Say you have a graph $G$ where the size of the largest independent set is $\alpha(G)$ Consider what happens if you delete a vertex from $G$ to get $G'$, then run the INDEPENDENT SET VALUE algorithm on $G'$ - what possible values can you get for $\alpha(G')$, and what does that mean for the vertex you deleted?


I am having trouble understanding (and implementing) logistic regression for classifying into three classes (For reference, i am using Kevin P Murphy's Book "Machine Learning: A Probabilistic Perspective" and implementing with MATLAN - without any toolboxes)

I have a dataset with 392 samples (rows), each sample has 8 features (columns), one of which defines the class (i.e. column 1 of features is divided into three equal bins which define the three classes - low, medium, and high).

I am having a really hard time understanding how to create a logistic regression model to classify a sample into one of these three classes.

I just finished learning and making a linear regression model where I learned about both the Ordinary Least Squares (Closed form) solution for the weight vector, and also Gradient Descent (Open Form) solution. But i never implemented gradient descent because my data was fitted perfectly fine with the OLS solution for weight vector.

I am extremely confused how to create a weight vector for Logistic regression, I understand that it requires use of Gradient Descent because there is no closed form solution. I also read about the Newton method for calculating the weights but I don't understand it at all.

And after you use these methods to calculate weights how do you apply the weights to the sample data? In Linear regression it was simply because you simply multiplied the weights by the features (and higher order features for higher order linear regression), but is it the same in logistic regression?

Moreover my understanding so far is that this model only works for binary classification, so how would i do it for three classes?

Basically my question boils down to this:

How exactly do you find the weight vector for logistic regression (using either gradient descent or newtons method, whichever is easier) and how do you apply the weight vector to the sample to get a classification out of it for 3 classes (not just two).

How do you apply the weight vector to the sample to get a classification out of it for 3 classes (not just two).

If you have $n$ possible classes then you must train $n$ logistic classifiers on your training data, with each classifier producing as output the probability that a given sample is a member of the class the classifier is trained to recognize.  Once training is complete, to classify a new sample you let all the trained classifiers try to recognize it and accept the judgment of the classifier that produces the highest probability value.  This is known as one-vs-all or one-vs-rest classification and is a standard way to use binary classifiers to do multiclass classification.

The weights are applied the same way in classifying new data as they are when you're training the classifier.  You have a weight vector $\theta$ containing coefficients that when combined with a sample's feature vector $x$ yield an hypothesis value.  For linear regression $\theta^T\negthinspace x$ (expanded: $\theta_0 + \theta_1x_1 + \theta_2x_2 +$ ...) yields the hypothesis value.  For logistic regression $\theta^T\negthinspace x$ is used as the exponent in the logistic function to produce the hypothesis value:

\begin{equation}
h_\theta(x) = \dfrac{1}{1 + e^{-\theta^T\negthinspace x}}
\end{equation}
$e$ is the usual natural log constant $\approx 2.71828$.

$h_\theta(x)$ is the probability that the sample $x$ is a member of class the classifier recognizes.  Compute $h_\theta(x)$ for each classifier and accept the verdict of the classifier that produces the largest probability value.

  How exactly do you find the weight vector for logistic regression (using either gradient descent or newtons method, whichever is easier)?

Gradient descent works the same way for logistic regression as it does for linear regression.  You're still trying to minimize the cost function by iteratively nudging the weights to better values using partial derivatives of the cost function.  The hypothesis function is different for logistic regression, but the way it is used in gradient descent is the same.  Once you've written code to do gradient descent for linear regression, you should be able to just plug in a different hypothesis function and have it work for logistic regression.

Pseudocode for one iteration of gradient descent:

newtheta := theta;
learning_rate := 0.01;
for k := 1 to n
   sum := 0
   for i := 1 to m
      sum := sum + (hypothesis(x[i], theta) - y[i]) * x[i][k];
   end
   nudge := sum * learning_rate;
   newtheta[k] := newtheta[k] - nudge;
end
theta := newtheta;

x is a matrix containing your training data, one sample per row.

y is a vector containing the correct classification prediction for each sample, 1 if the sample is in the class, 0 otherwise.

m is the number of samples.

n is the number of features.

The idea is that you would repeat this process until you reach some minimum and acceptable cost (error) over the training set.


Which of these simple data structures is most efficient when implementing a Dequeue? A deque is a double ended queue of course. So if I can either use 2 stacks, or 2 queues, or 1 stack and 1 queue, which two would I use to have the fastest implementation? Can we derive the complexity for InsertLeft, InsertRight, and RemoveLeft, and RemoveRight?

I was thinking of using 2 stacks. Call 1 stack 'left' and the other 'right'. All operations are now order O(1) because if InsertLeft inserts items at stack called 'left' and InsertRight inserts in stack called 'right'. Both stacks maintain the front and the end of the sequence respectively. Am I correct?

We need to clearly separate interface interfaces (abstract data types) from implementation. You talk about implementing a deque, an ADT, in terms of a stack or queue, but those are themselves ADTs. We need to be talking about concrete implementations.

So here's the answer (drumroll please): use a doubly-linked list. All the operations you mentioned are now $O(1)$.


Two languages such that their Kleene closures are equal I am trying to solve the following problem:
Find languages S and T over the alphabet $\{a, b\}$ such that $ S \not\subset T $ and $ T \not\subset\ S $ ($S$ is not contained in $T$ and not equal to $T$, $T$ is not contained in $S$ and is not equal to $S$) but $S^* = T^*$.
It might be trivial, but I would appreciate some help.

I had originally assumed that the sets are disjoint, but there's no such requirement in the question. I'll post my solution in case anyone might have the same problem in future.
S = {a, b, ab}
T = {a, b, ba}
S* = T* since the intersection has all the letters of the alphabet plus ab and ba can easily be obtained from a and b.


Anagrams solver based on transitions probability I have an English dictionary (text file) and the frequency of 2-grams, 3-grams and 4-grams as the beginning of each word. I need to write an algorithm that, with a given word, calculates the possible anagrams (which have to be into the dictionary) based on transitions probability (my assignment requires that I use this method).

I thought to use the Viterbi Algorithm  but I don't know if it is the right choise. What do you think about a simulated annealing algorithm? Can you give me any help or advice?

There's a better way to list all anagrams.

Given a word, compute its "canonical form" by sorting the individual letters into alphabetical order.  For instance, BASEBALL becomes AABBELLS.  Do this for each word in the dictionary, and build a data structure that maps from a canonical form to the list of words with that canonical form (e.g., from AABBELLS to BASEBALL) -- for instance, you might use a hashtable or a sorted list.

Now, given one English word, if you want to find all anagrams of it, you can rapidly compute all anagrams by computing its canonical form and then looking that up in your data structure.

This doesn't require n-grams, transition probabilities, Viterbi algorithm, or anything fancy like that -- just sorting and simple data structures.  Thus, it can be coded up quickly and elegantly; and it will be very efficient.


Find a sequence of integer powers faster than the naive algorithm Let $k\in \mathbb{N}$ be fixed. The naive way to compute a sequence of values $a_1^k,\ldots,a_n^k$ where $a_i\in \mathbb{N}$ for all $1\leq i\leq n$ is compute $a_i^k$ individually with the exponentiation by squaring. This takes a total of $O(n\log k)$ multiplications.

Is this optimal? What if for each $a_i$, we have $\frac{1}{c} a_i \leq a_{i+1}\leq c a_i$.

I come up with this question because I was doing a binary search over $f(n)=n^k$.

In the worst case, this seems to be optimal. If your $a_i$ are pairwise coprime,
e.g. $k$ different primes, they powers do not share any factors.

Of course, if $k$ is large but $c$ from your proposed restriction is small, there
may not be such a set; then, you powers share factors. You could exploit this
if you knew the shared factors for your $a_i$; but finding those is harder than
just computing all the powers.

So I daresay, no, you can not do this faster without more knowledge about the $a_i$.


Equivalence in finite sets of turing machines I have this exercise and I really don't know how to complete it:

Prove that for all finite sets S of Turing Machines it is decidable
whether or not given any two Turing Machines M1 and M2 in S they
recognize the same language, that is, L(M1)=L(M2)

I know that the problem of equivalence of languages is undecidable in general, but the additional hypothesis of the finiteness of the set S of machines does not suggest me any reason why this case should be different. Can somebody help me?

Hint: Since $S$ is finite, there are finitely many legal queries, and we can hardcode the answers to all of them.


Must $x$ and $y$ be different in a statement of the form $\forall x \forall y \cdots$? Given the following predicate formula $F$:

$$\forall x \forall y [(\text{italian}(x) \Rightarrow (\text{winWC}(y) \Rightarrow \text{happy}(x))]$$

I am having trouble understanding whether $x$ and $y$ must be different elements.

Also, I have been given the following statement:

  "Italians are happy if the Italian National team wins the world cup."

How can I prove that this is not equivalent to what is expressed by $F$? Should I bring both in CNF and then somehow argue they cannot be equivalent?

For any formula $\varphi$ in which $x$ and $y$ are free variables, $\forall x \> \forall y \> \varphi$ quantifies over all possible values for $x$ and $y$. As a result, $x$ and $y$ may be different objects or they may be equal; for the statement to hold, $\varphi$ must hold in both cases.

Following this reasoning, a valid interpretation for your formula would be "an Italian is happy regardless of who wins the World Cup" (assuming "WC" stands for "World Cup"), with "Italian" standing for $x$ and "who" for $y$. Thus, $x$ is happy if they win the World Cup ($x = y$) but also happy if someone else does ($x \neq y$); hence "regardless".

The other statement can be expressed in predicate logic as follows:
$$\forall x (\text{italian}(x) \to (\text{winWC}(x) \to \text{happy}(x)))$$

In fact, this evaluates to the same truth value as the first formula precisely when you pick the same values for $x$ and $y$.

Assuming the most reasonable domain (i.e., persons in the world) and interpretation in this setting, you could argue there is an Italian which is happy only if the Italian national team wins the World Cup and is unhappy otherwise. Pick this person as your value for $x$ and an arbitrary non-Italian (e.g., German) person for $y$; then the second formula evaluates to true under this variable assignment (since $\text{italian}(x)$ is true and $x$ is happy if $\text{winWC}(x)$, that is, the Italian national team wins), but the first evaluates to false (since $x$ is unhappy if $y$'s team, that is, the German national team wins).


What do I need to study in order to understand and design a programming language? What do I need to read in in order to :

understand the specs of an already made programming language
Design a programming language
Design a compiler and assembler for that language
make an architecture of a processor

I do not understand what is your intended meaning in "understand the
specs of an already made programming language". There are always many
things to be understood in a complex entity, and any understanding
must be related to a purpose.

If your purpose is just to understand how to program with this
language, understanding how it is implemented is not, and should not
be your problem. Certainly not at first. What you have to understand
is the high level concepts used in the language, and that may depend
very much on the language. You need to understand the style of
programming the language is promoting. All that comes to some extent
with the manuals and tutorials. But some concepts may require advanced
knowledge, some of which may be general, and some which may be very
specific. What you should learn will be clear from the manuals and
tutorials.

If you want general knowledge on language architecture, on the role of
syntax and semantics, on the main techniques useful to write compilers
and interpreters, you should get a book on compiler writing. Many will
do.  The most popular is probably the Dragon Book in one of its
successive edition.

To design a programming language, there is no specific study, other
than a good understanding of the structure and concepts used generally
in programming languages (see above). A good knowledge of logic and mathematical style cannot hurt. Knowing many programming languages with preferably very different styles is probably a prerequisite. The hard part is knowing why you
want to do it, and what for. A language is a vehicle for
communication. Hence, if you are alone using it you are wasting your
time (unless it is a proof of concept, which is usually related to
some advanced theoretical work). You have to have a purpose for your
language, and an idea that it is better for that purpose than other
languages that may already exist. If you still have to read what is
useful for designing it (other than general knowledge - see above),
you are not ripe for designing one. The needed knowledge must precede
the intent to design a language. It must be the expression of a need,
before it becomes a will. Actually this is often true of creative activity.

Languages are not necessarily general purpose languages. They may be
very useful without having Turing power. A language must be thought to
express some concepts in a given domain of discourse. For example,
languages like HTML, or TeX. are intended to express textual layout of
documents. They can be very sophisticated, but not intended to write
graph algorithms or matrix processing. Other languages may appear like
weak algorithmic languages because they have been designed to posses
specific properties that more general languages will not have, such as
automatic analysis of their computational characteristics. Some
languages may use specific kinds of parallel processing that are
easier to analyze and optimize.`Some of these specific languages, or
some features of more general languages require high mathematical
sophistication in specific domains.  Naming them here would just be
name dropping.

Regarding processor architecture, I cannot help you. It is largely a
different topic, though it does matter for some aspects of compiling,
and I am not competent.

If you want to see an interpreter written in half a page, that
implement a general purpose programming language that was actually
used a lot (in more sophisticated versions, to be honest), look for
the Lisp 1.5 interpreter. It is somewhere in this old book.


Regularity of a language contains more 1's than 0's The language of all bitstrings with more 1s than 0s, i.e.,

$ A = \{x: 2\Sigma_{i}^{|x|} x_{i} > |x|\}$ is regular.

I know I should apply Pumping Lemma and the proof as well, what I cannot understand is' the meaning of question itself. To be more precise, my question is' how the formal and informal sections of the question are the same?

Treat the characters of the string as integers and add them up. The number you get is the number of ones in the string. If that number is more than half the length of the string, then there are more ones than zeros.

In my opinion, that's not a good way to specify the language. It's clever and correct but, honestly, if somebody has to ask a Stack Exchange question about the way you chose to write "More ones than zeros", then you made it way too hard to understand.


Proof that L(M) = {accepts the string 1100 } is undecidable Let $$L_\ = \{\langle M\rangle \mid M \text{ is a Turing Machine that accepts the string 1100}\}\, .$$

To proof that the language $L$ is undecidable I should reduce something to $L$, right?

I tried with the classic $A\ TM$, but I could not figure out how to reduce properly.

How I can I proof that $L$ is undecidable?

The usual reduction from the halting problem: for example, the same reduction that shows the zero-input halting problem to be undecidable.

   Suppose you can determine whether a machine $M$ accepts some magic string (such as $1100$).  You can then decide whether an arbitrary machine $M$ halts when given input $x$ as follows. Produce a machine $M_x$ that ignores its input and simulates $M$ running on input $x$. If $M$ halts, $M_x$ accepts whatever input it was given; otherwise, $M$ doesn't halt so nor does the simulation $M_x$. So $M_x$ accepts the magic string if, and only if, $M$ halts on input $x$. Hence, if you could decide whether a machine accepts the magic string, you could decide the halting problem.


Must an optimization problem with a greedy algorithm belong to P? If it is known that for some optimization problem there is a greedy algorithm that solves it and the solution includes sorting of input at the preliminary stage, is it necessarily true that the problem belongs to P?
I was told it is true that problems of this type must belong to P, but I have questions about whether this is true.
It seems to me that there should be many examples of optimization problems with non-deterministic greedy algorithms.
Are there in fact counterexamples to this claim or is it necessarily true?

If the greediness here means moving on the input based on a specified score, and computation of the input item's score is polynomial, the answer is yes. It is correct.  Because moving on the input with $n$ items is linear, and if the scoring computation for each item will be polynomial, as sorting them will be polynomial as well; finally, we can solve the problem in polynomial time (by the greedy algorithm).
Notice that, the polynomial computability of the score is vital here. For example, if the computation of the score for each item will be an NP-complete/hard problem (for example if it is the minimum vertex covering of a graph), the statement will not be valid anymore.


Single machine job scheduling to minimize weighted sum of completion time Given $n$ jobs, schedule them such that the weighted sum is minimum.

weighted minimum sum S  for the schedule $\sigma = \{ J_1, J_2, ... J_n \}$ is given by :

$S = \sum_{1\leqq i \leqq n} w_i C_i$ where $C_i\ = \sum_{1\leqq j \leqq i} t_j$ and $w_i$ is the weight of job $J_i$,  $t_i$ is the time $J_i$ takes to complete.

I think the solution is to schedule the jobs in shortest weighted processing time i.e. to arrange them in the increasing order of  $ t_i/w_i $.

But how to prove this.

Hint: Let $\sigma$ be the optimal schedule. Suppose that jobs $k$ and $k+1$ are switched. How is the cost affected? What does the optimality of $\sigma$ tell us about $w_k,w_{k+1},t_k,t_{k+1}$?


Meaning behind 1/ϵ in FPTAS I am currently learning about FPTAS and PTAS but do not understand what the definition of FPTAS.

  A fully polynomial time approximation scheme (FPTAS) for problem $X$ is an approximation scheme whose time complexity is polynomial in the input size and also polynomial in $1/\epsilon$.

In this explanation, what does the $\epsilon$ stand for?

Suppose that your problem is a minimization problem: on instance $I$, you output a solution $O$ which should minimize some function $f(O)$. We say that an algorithm is a $(1+\epsilon)$-approximation if on instance $I$ it outputs a solution $S$ which satisfies
$$ f(S) \leq (1+\epsilon) f(O) $$
for an optimal solution $O$. We also say that $S$ is a $(1+\epsilon)$-approximate solution.

An FPTAS is an algorithm that gets as input an instance of size $n$ and a number $\epsilon>0$ (let's not worry about how $\epsilon$ is represented), returns a $(1+\epsilon)$-approximate solution, and runs in time $O(n^C (1/\epsilon)^D)$ for some constants $C,D>0$.

Given an FPTAS, you can extract a polynomial time $(1+\epsilon)$-approximation algorithm for any $\epsilon > 0$; furthermore, the dependence of the running time on $\epsilon$ is polynomial (in $1/\epsilon$).

A PTAS, in contrast, is an algorithm gets as input an instance of size $n$ and a number $\epsilon>0$, returns a $(1+\epsilon)$-approximate solution, and for any fixed $\epsilon > 0$, runs in polynomial time. That is, for every $\epsilon > 0$ there exist constants $A_\epsilon,C_\epsilon$ such that the running time of the algorithm is at most $A_\epsilon n^{C_\epsilon}$.

Again, given a PTAS, for any $\epsilon > 0$ we can extract a polynomial time $(1+\epsilon)$-approximation algorithm. This time, however, the dependence of the running time on $\epsilon$ can be arbitrary.


What type of operations are seen the most at the physical disk level — reads or writes? Why? This question came up in my operating systems class in a section about file system cache and RAID.

I'm speculating that the answer is that writes are seen more at the physical disk level because an efficient cache reduces the need to read from the disk.

Can someone confirm or correct this?

The proportion of reads to writes would be workload and system dependent. Before filtering by caching, reads will typically be more common, if for no other reason than code being read-only and data writes being dependent on at least an equal proportion of reads.

Under paging, discarding a clean (stored) page reduces the number of storage accesses, so there is an incentive for the OS to prefer paging out such pages. This biases toward reads (paging-in) at the storage level. (Obviously, allowing dirty pages to accumulate endangers responsiveness since eventually the best page to replace would be dirty so that demand for a not present page would be delayed by the required writeback. Maintaining a modest free list would ameliorate this issue.)

For an in-memory database (with persistence) or a log (or backup) server, writes would presumably dominate. In the former case reads are satisfied by memory by design; in the latter case reads are simply less common.

For many tasks oriented toward content consumption such as webserving and gaming where writes are much less common, storage reads can easily dominate even with caching.

Prefetching can also increase the number of read requests. If the cost of a read miss is high and the cost of an unused read is moderate, even somewhat aggressive prefetching can be beneficial.

The relative costs of reads and writes can also be a factor that can bias OS policies with respect to caching/prefetching. SSDs generally provide much higher read bandwidth than write bandwidth and do not penalize random accesses, reducing the cost of prefetching under low memory utilization.

Overprovisioning memory (in terms of cost per unit of work) can reduce the frequency of storage reads (moving toward the in-memory database model) and may be a reasonable design choice due to an impracticality of sharing memory across more work (and the non-linear cost per bit), a preference for responsiveness over average throughput, or a desire for load tolerance (i.e., the extra memory may not be worthwhile for average throughput or responsiveness but may avoid issues under high load).

Persistent (battery-backed or inherently persistent) memory can greatly reduce the number of writes to actual storage.

RAID will generally amplify the number of writes but not the number of reads seen by disks (RAID systems typically rely on the disks' internal error detection to detect read errors but write to more than one disk on a write).


Is this language countable : $L= \{ w : w \in (1 + 0)^{*} \}$ This is my take :

Epsilon ---> 1

0 -->  2

01 ---> 3

10 ---> 4

11 ---> 5

001 ---> 6

010 ---> 7

.
.
.

So therefore we can count them.

But  based on this video : https://www.youtube.com/watch?v=oe-ZAJQz9Cc&index=5&list=PLsFENPUZBqiqbnD-WatYxUhRWLMNDoMun

They should not be countable, but i did not understand that video, the guy says all possible languages over $\{0,1\}^{*}$ are uncountable!

The language $$L= (0+1)^*$$ (the set of all strings over $0$ and $1$) is countable. Furthermore, any subset of $L$ is also countable. However, the set of all sublanguages of $L$
$$S = P(L) = \{M \mid M \subseteq L\}$$ (a set of sets in fact) is not countable. This video proves this using the diagonalization argument.

$S$ and $L$ are two different sets. In fact, $L$ is a member of $S$.