Write through and write back cache policies There are Two Write Hit policies: Write Through  and Write back
There are Two Write miss policies: Write Allocate and No Write
Allocate
There are two memory access techniques: simultaneous and
hierarchical access

Can any gentleman PLEASE write formulas for different combinations ?

I am having very important competitive exam that can change my life, and i am struggling with these methods badly.

For instance one may consider following example and please show me relevant modification of this example.
Question : In a certain system the main memory access time is 100 ns. The cache is 10 time faster than the main memory and uses the write though protocol. If the hit ratio for read request is 0.92 and 85% of the memory requests generated by the CPU are for read, the remaining being for write; then the average time consideration both read and write requests is

a) 14.62ns

b) 348.47ns

c) 29.62ns

d) 296.2ns

PS:- I know meaning or working of all techniques but don't know how can i drive formulas.
Please do it, i really need that badly. It would be GREAT help.

Thnks in advance.

When you want a general formula for a particular case, just derive it.

Let the main memory access time be $x$, and the cache access time be $y$. Let the hit ratio be $h$ and the fraction of requests that are reads be $p$.

Now,
$$\begin{align}\text{Average access time}&=\text{Weighted average of read and write times}\\&=\text{Fraction of reads}\times\text{Average read time}+\text{Fraction of writes}\times\text{Average write time}\tag1\end{align}$$

Let us now go through the read process. Firstly, there are two possibilites - a cache hit or a miss. If it is a hit, the cache access time is the total read time. If it is a miss, then the total read time is the sum of the time taken to access the cache and the time taken to access the memory. The fraction of hits is given by the hit ratio. Again, we take the weighted average.

$$\begin{align}\text{Average read time}&=\text{Fraction of hits}\times\text{Cache access time}+\text{Fraction of misses}\times(\text{Cache access time}+\text{Memory access time})\\
&=hy+(1-h)(x+y)\tag2\end{align}$$

Now, the writes. It is given that the write policy is the write through policy. This means that when a write is made, irrespective of a hit or a miss, memory is accessed as well. As the memory access time dominates over the cache access time, and the hit ratio for writes is not given, ignore the difference in the times of accessing just the memory and accessing the cache and the memory.

$$\begin{align}\text{Average write time}&=\text{Main memory access time}=x\tag3\end{align}$$

Combining $(1),(2),(3)$, we get,
$$\begin{align}\text{Average access time}&=p\left[hy+(1-h)(x+y)\right]+(1-p)x\end{align}$$

Here, $p=0.85,h=0.92,x=100\text{ns},y=10\text{ns}$. Substituting,
$$\begin{align}\text{Average access time}&=0.85\left[0.92\times10+(1-0.92)(100)\right]+(1-0.85)\times100\\
&=0.85\times17.2+15\\
&=29.62\text{ns}\end{align}$$

Similarly, you can attempt the other cases mentioned in your question.


Average runtime of naive primality test The naive prime test goes something like this:

is_prime(n):
  for(i=2; i<=sqrt(n); ++i):
     if n mod i == 0 :
       return false
  return true

If $n$ is prime the loop runs for $\sqrt(n)$ iterations. I was wondering what the "average" runtime is. It is of course troublesome to define this properly, because there is no uniform distribution on the natural numbers, so I don't know whether this question actually makes sense or not. My intuition is that "most" numbers have relatively small divisor and prime numbers are relatively rare.

Maybe the following definition works: Let $f(n)$ be the number of loop iterations necessary for testing the first $n$ numbers using the above function. What is a good upper bound for $f(n)/n$?

Better suitable for math.stackexchange.com.

It is quite widely known that about n / ln (n) numbers are primes, so you get $n^{1/2}$ iterations in about n / ln (n) cases.

You can try to figure out how often you have more than $n^{1/3}$ iterations: That happens if there is no prime factor less than $n^{1/3}$, and therefore the number is either prime or the product of two primes. So you either have a prime, and there are about n / ln n of those, or you have a product of two primes, that is a product of one prime p from $n^{1/3}$ to $n^{1/2}$, and one prime from p to n/p, and there only about (n/p) / ln (n/p) of those.

All other numbers take less than $n^{1/3}$ iterations.


Has there been a lexer that takes in much more than a regular language? I understand the restrictions, because a regular language is expressive enough to allow all types of tokens. And even if some context is needed in many languages to tokenize properly, they all seem to be "approximately" regular languages.

Yet I would be interested if any attempt in any programming language, possibly esoteric language, has been taken to completely eschew the conventional division between type-3 lexers and type-2 parser.

FORTRAN is famous for having some difficult to lex constructs, but those difficulties result probably more from having been designed before the classification was established (or at least known in programming circles)
Several languages are described with a type-3 lexers but some characteristic are easier to handle by feeding information from the parser to the lexer (C/C++ typedef, C++ templates, Ada/VHDL attributes)
Several languages have layout rules (Python, Haskell) which are usually not described as type-3 lexers (I don't know if it is possible to do so or not)


Description of lists with functions in LISP I have been given the following implementation of basic list functions in LISP:

nil = (lambda (k) (k ’none ’none))
(cons x y) = (lambda (k) (k x y))
(car l) = (l (lambda (x y) x))
(cdr l) = (l (lambda (x y) y))
(null? l) = (l (lambda (x y) (= x ’none)))

As an intent to show that data can be constructed using only pure functions.

I don't understand very well this code. For starters, what's the role of k? Can you show how I can come up with this implementation? Basically, I'm looking for some intuition on how this works and if you can show in some manner how you deduce the implementation.

In PL theory, this is known as (a variant of) the Church-encoding of pairs.

The idea is the following: assume for the moment you only have a language with primitive  booleans (true, false, if-then-else) and primitive (first-class) functions. Pairs are not primitive, yet they can be encoded as follows.

In place of a pair $(x,y)$ we can consider the following function:
$$
p(b) = {\sf if}\ b \ {\sf then}\ x \ {\sf else}\ y
$$
It is immediate to verify that $p({\sf true}) = x$ and $p({\sf false}) = y$. So this function $p$ indeed encodes the information which lies inside a pair. Projections can then be defined as
$$
\pi_1(p) = p({\sf true}) \qquad
\pi_2(p) = p({\sf false})
$$
while the pair constructor becomes
$$
cons(x,y) = \lambda b.\ {\sf if}\ b \ {\sf then}\ x \ {\sf else}\ y
$$

Now, suppose we no longer have primitive booleans/conditional, but only have functions. We can still obtain something which behaves as a boolean through this encoding:
$$
{\sf true} = \lambda x y. x \qquad
{\sf false} = \lambda x y. y \qquad
$$
and (since now a boolean $b$ is a "binary" function)
$$
{\sf if}\ b \ {\sf then}\ x \ {\sf else}\ y = b x y
$$
It is immediate to verify that
$$
{\sf if}\ {\sf true} \ {\sf then}\ x \ {\sf else}\ y = {\sf true} x y = x
$$
and the $\sf false$ analogous.

Once you combine both encodings, you get that
$$
\begin{array}{l}
cons(x,y) \\
= \lambda b.\ {\sf if}\ b \ {\sf then}\ x \ {\sf else}\ y \\
= \lambda b. b x y \\
\end{array}
$$
and
$$
{\sf car} = \pi_1 = \lambda p. p {\sf true} = \lambda p. p (\lambda x y. x)
$$
and its $\sf cdr$ analogous.

The LISP encoding you have is very similar to this encoding: it only have a few more twists for encoding $\sf nil$ as well, but that's a minor point.

The variable name $k$ which appears there in place of the "boolean" $b$ likely stands for "continuation", which is a key notion in PL theory.


Understanding truncation and rounding error in IEEE floating point system? I'm trying to understand the theory behind finding the optimal $h$ value for differentiation in this definition:

$$ \frac{f(x+h) - f(x)}{h}$$

as $h$ tends to 0.

Here is my understanding:

Truncation error comes from say approximating the value of $f(x+h)$ using the taylor series. In this case, it could be that:

$$ f(x+h) \approx f(x) + hf'(x) + \frac{h^2}{2!}f''(x) + O(h^3)$$

Letting $f'(x)$ to be the subject since we want to find gradient $f'(x)$, we have

$$f'(x) = \frac{f(x) - (hf'(x) + \frac{h^2}{2!}f''(x) + O(h^3))}{h}$$
$$\implies f'(x) = \frac{f(x+h)-f(x)}{h} - \frac{h}{2}f''(x) + O(h^2)$$

Intuitively, we can stop at here by letting $h \approx \sqrt\epsilon$ where $\epsilon$ is the machine epsilon, we can thus limit our truncation error. But suppose we continue, then our truncation error is $\frac{h}{2}f''(x)$.

Then rounding error comes from the interaction of the sums in the differentiation equation:

$$ \frac{f(x+h) - f(x)}{h} = \frac{[f(x) + hf'(x) + O(h^2)] - f(x)}{h}$$

But for $f'(x) \approx 1$ and since we have $h \approx \sqrt \epsilon$, we have

$$ \frac{f(x+h) - f(x)}{h} \approx 1 \pm \frac{\epsilon}{h}$$

Which means the rounding error is approximately $\frac{\epsilon}{h}$, which concurs with the fact that the left hand side of the equation is actually $f'(x)$ as well, just that we have managed to reduce the rounding error to what is seen on the right hand side.

Now, we see that our truncation error varies linearly with $h$ while our rounding error varies inversely with $h$. To find the optimal $h$ value, we equate both errors:

$$\frac{\epsilon}{h} = \frac{h}{2}f''(x) \approx \frac{h}{2}$$ since we have $f''(x) \approx 1$.

Letting $h$ be the subject, we have $$h = \sqrt{2\epsilon}$$ which means the optimal $h$ is around $h = \sqrt{\epsilon}$ as expected.

Is my understanding correct? Does the final factor of 2 in the end matter?

Big problem in the above argument: in point 3, one already use the fact that $h = \sqrt \epsilon$. Wouldn't that already defeat the purpose of finding the optimal $h$?

As listed your reasoning is indeed circular: you start by assuming $h \approx \sqrt{\epsilon}$, then use the results in point 3 to infer that we should take $h \approx \sqrt{\epsilon}$.  So that's not convincing.  So let's redo the analysis more carefully, then we'll look at the meaning of the constant.

A more careful analysis

As in your analysis, we'll assume $f'(x) \approx 1$ and $f''(x) \approx 1$.

Your analysis of truncation error is fine; the truncation error is indeed $\frac{h}{2} f''(x) + O(h^2)$, which given your assumptions is $\frac{h}{2} + O(h^2)$.  In our analysis $h$ will be small enough that $O(h^2)$is negligible, so we'll call the truncation error $\frac{h}{2}$ for simplicity.

What about rounding error?  The rounding error of representing $f(h)$ in floating point is $\epsilon$ in relative error, where $\epsilon$ is the machine epsilon; in absolute error, that is $\epsilon f(h)$.  Since you assumed $f(h) \approx 1$, that is $\approx \epsilon$.  Similarly, the rounding error of representing $f(x+h)$ is $\epsilon f(x+h)$ in absolute error; since $f(x+h) \approx f(x) \approx 1$, that is $\approx \epsilon$ as well.  Now the absolute error of $f(x+h)-f(x)$ is at most about $2\epsilon + \epsilon (f(x+h)-f(x))$; the $2\epsilon$ comes from the error in each of the two subterms (and the triangle inequality), and the $\epsilon (f(x+h)-f(x))$ comes from roundoff error in representing the result.  Since $f(x+h)-f(x) \approx h f'(x) \approx h$, that means the absolute error of $f(x+h)-f(x)$ is at most about $2\epsilon + \epsilon h$.

Then we divide by $h$.  The absolute error becomes $2\epsilon/h + \epsilon$, plus a term due to representing the result in floating point; that extra term is $\epsilon ((f(x+h)-f(x)/h)$, and since $(f(x+h)-f(x)/h \approx f'(x) \approx 1$, we see that the extra term is $\approx \epsilon$.  Therefore the absolute error in computing $(f(x+h)-f(x)/h$ is about
$2\epsilon/h + \epsilon + \epsilon$.  So, the total roundoff error is about $2\epsilon/h + 2\epsilon$, in absolute error.

The total error is at most the sum of the truncation error and the roundoff error, or about
$$\frac{h}{2} + {2\epsilon \over h} + 2\epsilon.$$
We want to know what value of $h$ minimizes this expression.  We can figure that out by letting $g(h) = \frac{h}{2} + 2\epsilon/h + 2\epsilon$ and minimizing $g(h)$; the minima must be at a point where the derivative is zero.  So, differentiate:
$$g'(h) = \frac{1}{2} - {2\epsilon \over h^2}.$$
Setting $g'(h)=0$ and solving for $h$ yields $h^2 =4 \epsilon$, i.e., the function $g(h)$ is minimized at $h=2\sqrt{\epsilon}$; at that point, we have a total (absolute) error of at most $g(2\sqrt{\epsilon}) \approx 2 \sqrt{\epsilon} + 2 \epsilon \approx 2\sqrt{\epsilon}$.

The summary: assuming $f(x)\approx 1$ and $f'(x) \approx 1$, the total error is minimized when you choose $h$ to be about $h\approx 2\sqrt{\epsilon}$.  If you choose $h$ too much larger than that, the truncation error increases and starts dominating.  If you choose $h$ too much smaller than that, the roundoff error increases and starts dominating.

So, if you know $f(x)\approx 1$ and $f'(x) \approx 1$, then it's reasonable to choose $h\approx 2\sqrt{\epsilon}$.

The constant

Now, you might be wondering a bunch of things.  Why the constant 2?  Where did that come from?  How critical is it for the constant to be 2?  What if I use $h \approx \sqrt{\epsilon}$ instead of $h \approx \sqrt{2\epsilon}$?

Well, if you redo the calculation with a different value of $h$, you'll see that the total error is not too sensitive to the constant 2.  For instance, if you choose $h=\epsilon$, then the total error will be at most about $g(\epsilon) \approx  2.5 \sqrt{\epsilon} + 2 \epsilon \approx 2.5 \sqrt{\epsilon}$, which is not that different.  So don't worry too much about the exact value of the constant.

Where did the constant 2 came from?  Well, partly it is coming from the fact that we are doing multiple operations, and you can get a little bit of roundoff error from each operation, so the error can accumulate.  And, partly it is coming from the assumptions that $f'(x) \approx 1$ and $f''(x) \approx 1$.  Of course, those assumptions are pretty sketchy.  In practice, we don't know what $f'(x)$ is before doing the computation (that's the whole point of this computation; we are trying to estimate/compute $f'(x)$), and we don't know what $f''(x)$ is.  So, that assumption also looks circular.

But here's why in this case it might be OK.  You could redo the calculation with different assumptions, e.g., $f'(x) \approx 2$ and $f''(x) \approx 3$.  If you do that, you'll find a slightly different optimal value of $h$; instead of $2 \sqrt{\epsilon}$, you'll have a slightly different constant replacing the 2.  So we can see that the 2 comes from the assumptions about the magnitude of $f'(x)$ and $f''(x)$.  But, crucially, if $f'(x)$ and $f''(x)$ aren't too large or too small, then the resulting constant in the optimal choice of $h$ won't be too different.  It might be $5 \sqrt{\epsilon}$ or $0.5 \sqrt{\epsilon}$, but that's not so bad.

And, in practice, we're often dealing with smooth functions where the derivatives don't get too large, so while we don't know exactly what $f'(x)$ or $f''(x)$ are, we might be able to assume they won't be too large.  As a result, taking $h \approx c \sqrt{\epsilon}$ for some small value of $c$ will be optimal.  We don't know what the optimal value of $c$ is exactly, but we can just heuristically pick a small value for $c$, like $c=1$ or $c=2$, and even if that's not exactly optimal, we'll probably do reasonably well -- it won't be too much worse.

So, the final answer is: no, the 2 is not essential.  It's perfectly reasonable to use $h = \sqrt{\epsilon}$ instead of $h = 2 \sqrt{\epsilon}$ -- but you probably want to choose $h$ somewhere in that neighborhood.


Solving a variant of the Exact cover problem I am trying to solve a variant of the Exact cover problem where every element has to be covered exactly twice instead of once ( i.e. has to be in exactly two sets that are part of the cover).

Now, it is clear to me that this is an NP-complete problem, but I wish to know if there is any hope for some pseudo-polynomial time algorithm to solve this problem.

If relevant, the context arose from trying to recreate polyhedra from their edges: given a set of edges, decide if they constitute some polyhedron, and if they do, give a set of its faces. Thus the set I wish to cover is the set of edges, and the collection of subsets I have is that of objects that can possibly be faces (each containing the edges of the corresponding "face")

There's no pseudopolynomial algorithm for exact cover (unless P=NP), so it is easy to show that this implies there is no pseudopolynomial algorithm for twice-exact-cover, either.

For instance, here's an easy reduction.  Given an instance $(S,X)$ of exact cover (where $S$ is a collection of subsets of $X$), let $X' = X \cup \{a\}$ where $a \notin X$ is a new symbol, and $S' = S \cup \{X', \{a\}\}$.  Now there is a twice-exact-cover for $(S',X')$ iff there is an exact cover for $(S,X)$.  So, if you could solve twice-exact-cover in pseudopolynomial time, you could solve exact cover in pseudopolynomial time, too.


implementing simple elvator algoirthm I want to implement simple elevator algoirthm.

people in different floors orders the elevator and the destination floor they want to get to (so you get a {from,to} alert from different floors).

So I got a simple strightforward solution :

once elevator start going in specific direction (lets say up) it will continue doing so , and serve all request of ppl want to go up (only if at the time they were made they were from higher floor in respect to the elevator) until serving the last one. all the request will be kept in an array, so on each floor you can check if someone wants to go on the same current direction.

In addition ill save in two vars (on for up direction and one for down direction) the highest and lowest points of request - hight floor that somebody wants to go up from there , and lowest floor that sombody want to get to lower floors from there - and the elevator allways will be  travling between these two points picking all the ppl that want to go on the same direction.

Does this solution make sense/work ? is there something as simple that make more sense?

I saw some priorities queue suggestions while searching in google but didnt really understand what the need of them ..

Thanks for your feedback .

Of course your approach will work but the answer to your question: "Does this solution make sense?" is entirely dependent on the situation.

Priority Queues are used (e.g.) when you want to serve the passenger whoever's destination floor is closest to the current one. Said passenger will have very high priority. This has a disadvantage that when a passenger wants to go to a floor that is far away from the current one,  he will be assigned a very low priority and will be served never/late. This can be solved by increasing the priority for a passenger over time.

Your approach has the advantage that there's a maximum waiting time known for all passengers. That is, the time it takes for a person to go to floor 1 when he gets in at floor 2 while the elevator is going up all the way to the penthouse and it stops at all floors along the way. The advantage of knowing this isn't present in the case (or it is at least not easy)  in the priority queue approach. But you can imagine that the situation described can be very annoying for the involved passenger since he will have to travel along the full building almost twice to lower just one floor.

Another approach I'm thinking of while writing this makes use of priority queues where the priority of going to a floor is the number of people that needs to get in/off at that floor.

In conclusion,  I think the advantage of your approach isn't very useful and it has a big disadvantage as well. I would look into priority queues and then define for yourself what priority means. Maybe your priority is to deliver groups of people to floors at once (last approach) or maybe it's to deliver the passenger whoever's floor is closest, (first approach). As said before,  deciding if an approach is good depends entirely on the situation.


Algorithm for type conversion / signature matching I'm working on an expression typing system and looking for insights on what algorithms may be available which solve my problem -- or a proof that its complexity is too high to be reasonable to implement. The problem is defined below.

I have a set of types which form a directed graph $T = (V,E)$ (assume no cycles). This graph represents the allowed type conversions in a language. For example an edge $e_i = v_1 \rightarrow v_2$ indicates that $v_1$ can be implicitly converted to type $v_2$.

I have a set of parameter types for a function expressed as a set $P = { p_1 ... p_n : p_i ∈ V }$. I also have a list of functions $F$ that might be applicable at this point. Each function has a signature (the types it accepts) $F_j = { f_1 ... f_n : t_i ∈ V }$.

The goal is to use a series of type conversions allowed by $T$ to convert $P$ into a signature compatible with any function in $F$. Conversion means moving along an edge in the graph to another type. Compatible means the converted parameter types match the function types.

If each conversion has a cost of 1, which function, if selected, has the minimum total conversion cost for all parameters?

A very simple example: Assume we have a graph of types integer -> real -> complex. Our parameters have the types { integer, real }. We have a function with types { complex, complex }. The first integer takes two conversion to match complex, and the real takes one conversion, for a total cost of three. We have another function with types { real, real }. This has a cost of one and is thus the better match.

My initial idea is to treat the search as a path through a graph and use a modified A* algorithm. Each of the possible functions is a goal in that graph, and each path between nodes represents the conversion of a single parameter type. With even a modest number of allowed type conversions however this becomes very inefficient.

I would suggest first solving the all-pairs shortest distance problem on the graph $T$ (or at least the single source version for each $p_i$ as the source) using standard approaches. Then, for each function signature $F_j=f_1,\dots,f_n$, compute $\sum_{i=1}^nd(p_i,f_i)$, where $d(p,f)$ is the distance between $p$ and $f$ (which can be infinite if $f$ is not reachable from $p$), then take the function that achieves the minimum. You should be able to do this in $O(|V|^3+nm)$ if you have $n$ parameters and $m$ functions.


Scoring the postal code mismatch I have two postal codes (fixed size of 6 digits) to compare and return the mismatch score.
where the mismatch weight of initial indexes is higher, then keep reducing.

Example postal code 123456, with index[0] ==> 1 is northern region, and if index[0] ==> 2 is southern region. so it should have very high mismatch score 123456 and 223456. index[1] represents sub-region like state, index[3] is like county/district, and so on..
But maybe 111156 and 111160 are nearer sub locality should be having less mismatch score.

The output of my result should match the score in the percentile.

To achieve this, if I take weights like this Sum[0.45, 0.15, 0.1, 0.1, 0.1, 0.1] == 100% but fixed weights cannot differentiate index base, e.g. for input source postal 111111 than searching with 111152 is greater mismatch than searching with 111125 as if we sum the mismatch scores. Mismatch weights percentile [0.45, 0.15, 0.1, 0.1, 0.1, 0.1] states, if there is a mismatch, happens at index 2, 3, 4, 5 all has a penalty of 10%, but this results in 111152 and 111125 will have same mismatch score for actual postal code 11111. So we cannot differentiate between 111152 and 111125. But you see 111125 is closer to 111111.
This makes me think of cumulative percentile index percentile like [1, 0.55, 0.4, 0.3, 0.2, 0.1] but this also doesn't work. As the sum of mismatch score going more than 1.

Also, it is not worthy to rely on the difference of postal code, like `111000 - 110999`, though it has a difference of 1, this difference same for `111000 - 111001`.
Hence `(((double)diff/Math.pow(10, diff.length()))` is also not working to compute.
So taking diff between two postal code as 123 then
123/1000 * (penalty[diff.length()]) wont work, as we cannot directly rely on difference.

Examples:
If i prefer mismatch penalty like { 0.8d, 0.7d, 0.6d, 0.3d, 0.15d, .05d }
0.05% penalty if the last char is not matched.
0.80% penalty if the first char is not matched.
Apply some minor penalty for every mismatch; after the first mismatch.

{"input" , "toBeCompared", "matchScore"}
{"999999", "989999", 0.29}, //71% mismatched, 29% matched
{"999999", "998999", 0.39},
{"999999", "999899", 0.7 },
{"999999", "999989", 0.85},
{"999999", "999998", 0.95}, //95% matched

Also should be able to differentiate scores between varying numbers.
{"111225", "111223", 0.949},
{"111225", "111229", 0.948},

How to achieve this? Kindly help.

If I understand you correctly, a minor modification of the absolute value should work, where you do digit-wise absolute difference and keep the magnitude:
$$
\sum_i \left| x[i] - y[i] \right| \cdot 10^{i}
$$
or in Python:
def dist(x, y):
    xs, ys = str(x), str(y)
    l = len(xs)
    diff = lambda a, b, i: abs(int(a[i]) - int(b[i])) * 10**(l-i-1)
    return sum(diff(xs,ys,i) for i in range(len(xs)))

To illustrate with your examples:
dist(111111, 111152) = 41 > dist(111111, 111125) = 14

dist(111000, 110999) = 1999 > dist(111000, 111001) = 1

You say (south v north) that this should be a very large diff, and that it is:
dist(123456, 223456) = 100000


Is $\log{n}$ bounded from above by $n^{o(1)}$? Let $O(n)$ be "Big-O" of $n$ and $o(n)$ be "Small-O" of $n$.

It is a well-known fact that $O(n \log{n}) \subset O(n^{1 + \epsilon})$ for any $\epsilon > 0$. Can we omit the $\epsilon$, and just type $O(n \log{n}) \subset O(n^{1 + o(1)})$?

Consider the function $f(n) = n^{1 + \frac{1}{n}}$ which I guess you'd say is in "$O(n^{1 + o(1)})$". I'm not sure you can call it polynomial, though.

Now, compute

$\qquad \displaystyle \lim_{n \to \infty} \frac{n^{1 + \frac{1}{n}}}{n \log n} = 0$,

so you have in fact that $f \in o(n \log n)$. Therefore, functions in this funky class of yours are not even (all) asymptotic upper bounds for $n \log n$.

The difference is that $\varepsilon$ ensures a non-vanishing distance from $n^1$ whereas $o(1)$ means that functions of the form $n^{1 + o(1)}$ in fact converge towards $n \in o(n \log n)$.


How to determine number of instances for resources in a resource allocation graph? I am struggling to determine the number of instances a resource will have. I have performed extensive research on this, but unfortunately have come up short. I am tasked with drawing a resource allocation graph and I have been provided with the number of processes which is 3 and the of resources which is 5. I have concluded that when drawing the resource allocation graph, I will need to know the number of instances of a resource. Please could someone just help in how I would go about working out or determining the number of instances a resource will have?

The number of instances should technically be specified to you. The best I can suggest is assume that each resource will only have one instance each. But I suggest getting more information on your scenario


Why do we use several bits instead of a single bit for storage of objects in Bloom Filters Bloom filters are a variant of hash tables except it is much more space efficient at the cost of a low probability of false positives .

How it works : Assume there are 10000 bits , 3 hash functions and an object Foo is to be inserted into the Bloom Filter .

Insertions : Foo will be hashed by the 1st hash function and the 3405 bit index is set to 1 , Foo is hashed by the second hash function and the 1001 bit index is set to 1 , Foo is hashed by the third hash function and the 5555 bit index is set to 1 .

Check exist : Foo will be hashed to the three different hash function and if all the bits at the respective index is set to 1 , the object is said to exist with a small chance of false positive else the object cant be found .

My question is : Why do we use more than 1 (in this case 3 bits ) to determine if a objects exist in the Bloom Filter , doesnt it increase the chances of collision with other objects which may also set the same bit to 1 . To me , it seems best to use a single hash function as it saves the most space (1 bit only) and least chances of collision with other objects in the Bloom Filter

Consider Bloom filters in which $k$ hash functions are used. If we look up a value which is in the filter, then we always conclude that it is indeed in the filter. Things are more complicated when we look up a value which is not in the table; we could erroneously conclude that it were in the table.

Suppose the filter is of size $n$, and $m$ values were put into the table. So roughly $km$ positions are set to $1$. If we look up a value which was not put in the filter, then assuming that the hash locations corresponding to it are random, the probability that we erroneously conclude that it is in the filter is
$$ \left(\frac{km}{n}\right)^k. $$
The correct value of $k$ thus depends on the expected $m/n$. Suppose that $m = n/10$. Then we have the following error probabilities:
$$
\begin{array}{c|l}
k & \text{error probability} \\\hline
1 & 0.1 \\
2 & 0.04 \\
3 & 0.027 \\
4 & 0.0256 \\
5 & 0.03125
\end{array}
$$
So in this setting the error probability is minimized for $k = 4$. Since $k$ also effects the running time, we might as well choose $k = 3$ for these parameters, for which the error probability is almost as good.


$P = NP$, what am I missing? First post here so hope I'm not missing too many guidelines.
I've had this idea for a few weeks now and I can't myself see where I'm going wrong with it, hope it makes some sense to you and thanks in advance for the help.
Here we go:
Assuming we could solve a NP-complete problem in logn SPACE, e.g. TSP. Then by reachability we could show that $P = NP$.
The machine will keep track of this information:

$\log n$ nodes for a path walked, call this memory pathMem
$\log n$ nodes for a reconstructed path walked, call this memory pathMemTemp
$\log n$ numbers indicating the chosen path, call this chosenPathNums
$\log n$ nodes for ending nodes of each path, call this endMem
some representation of the cost of the walk.

Step 1: Walk $\log n$ steps, note down the $\log n$ walked nodes in pathMem
Step 2: Check that there are no duplicates in pathMem (that means that you've walked $\log n$ unique nodes).
Step 3: Use a modified version of Savitch that counts the number of possible paths between start node and last node in pathMem. This should be at most $(\log(n)!)$ paths, represented in that number using binary and we get $O(log(log(n)!))$
Step 4: Find which of these paths that is in pathMem. Save that number in chosenPathNums at pos 1.
This gives us a deterministic way of refinding a specific path.
Step 5: Move last node in pathMem to endMem pos 1, clear pathMem.
Step 6: Walk $\log n$ steps from node at endMem pos 1, note down walked nodes in pathMem.
Step 7: Check that there are no duplicates in pathMem (that means that you've walked $\log n$ unique nodes).
Step 8: Reconstruct path that was taken from start node to node at endMem pos 1 by using Savitch's and the chosenPathNum, save it in pathMemTemp.
Step 9: Check that pathMem and pathMemTemp has no overlap. If there is overlap, halt with no, otherwise continue.
Step 10: Find the path number that is in pathMem. Save that number in chosenPathNums at pos 2.
Step 11: Move last node in pathMem to endMem pos 2, clear pathMem.
Step 12: Rinse and repeat, now checking pathMem vs start->(endMem pos 1) and then (endMem pos 1)->(endMem pos 2) etc., until you've walked $n$ nodes, thus having $\log n$ nodes in endMem and $\log n$ numbers in chosenPathNums.
Step 13: Calculate distance walked, check if less or equal to threshold.
This algorithm could be turned deterministic by looping every possible $\log n$ walk that is found from a node to another node.

It is not clear what is your question, but I will guess that it is "what is my mistake in my proof of $P = NP$?"
In addition to the fact that the algorithm does not guarantee to find the minimal path (because the algorithm cant deterministicaly choose the endMem nodes), the number of possible $\log n$-walks given $\log n$ nodes is not polynomial: $(\log n)! \sim \left(\frac{\log n}{e}\right)^{\log n}\sqrt{2\pi\log n}\sim \frac{\sqrt{2\pi\log n}}{n}e^{\log n \log \log n}\sim \sqrt{2\pi\log n}\times n^{\log\log n - 1}$.
As for the space complexity, to check there are no overlap between two $\log n$-walks, you need to keep track of the whole path (and not only two consecutive $\log n$-walks). That needs $\Omega(n\log n)$ space ($n$ nodes with a binary encoding of size $\log n$). So the corresponding Turing Machine use polynomial space, not logarithmic space.


Random restart technique definition I have stumbled across this question about the Random restart algorithm in search problems:
Random restart is technique which used for:
a)algorithms for search in space state when they get stuck
b)algorithms for informed search for better solution
c)algorithms for uninformed search for better solution
d)algorithms for local search for better solution
My thoughts are : it's a) or d) but I cannot decide since random restart is used for local search but we don't need better solution, however I haven't found anywhere that random restart helps us getting unstuck?

Welcome to the Computer Science Stack Exchange.
We have two subjects in search algorithms: Exploration and Exploitation. Now, Random Restart increases Exploration in your search.
There is no guarantee that random restarts help you to find better solutions. But it will give you this chance to search the space solution better.
So, The answer to your question is that random restart doesn't necessarily help us get unstuck. According to the above facts, (a) is wrong. Between the other choices, I pick the last one (d). I think random restart doesn't belong to informed and uninformed search.


Proving that a derived language is regular Suppose I have a DFA recognizing a regular language $L$, how do I prove that
$$\text{lefthalf}(L)= \{ w_1 \mid \exists w_2 \in \Sigma^* ,w_1w_2 \in L \land \|w_1\| = \|w_2\| \}$$ is also a regular language?

Hint: while reading $w_1$, guess $w_2$ and gather enough information so that in the end you can decide whether $w_1 w_2 \in L$.


R-Tree multipath search - remember the path? R-Trees can take several paths to retrieve an item because of overlaps in data being indexed or index structure. However, if we run the same search many times on the same unmodified structure, can we remember the correct path and avoid taking the wrong path?

Maybe caching the correct path? But I'm not so sure that R-Tree implementations do this or that R-Trees fully loaded in memory do this either.

Sure, you can cache the results of lookups into a R-tree (or any other data structure).  Simply build a cache (e.g., a hashtable) where after each lookup into the R-tree, you update the cache; and before doing a lookup into the R-tree, check the cache first.  You don't need to store the entire path in the cache: it's enough to just store the results of the search.

Whether this will improve performance or not will depend on your particular workload.


Finding closest edge to a point in a planar graph I have a point location problem (in a planar graph) with a twist: rather then finding which region the point is located in, I would like to find the closest segment (edge) to a point, ideally with a O(log n) complexity.
So far I was not successful in finding any reference that would discuss this specific problem. Is there any treatment you know of?
For this problem, we can assume that the graph is embedded in a Euclidian plane in a known way, where vertices are mapped to points and edges are mapped to straight line segments.

Use a Voronoi diagram of the line segments
As @D.W. noted, a Voronoi diagram of line segments1 is the usual way to approach this problem. It is possible to construct such a diagram via a modification of the Bentley-Ottman sweep-line algorithm for ordinary Voronoi diagrams (on points), see for example Section 7.3 of Computational Geometry by de Berg et al. But I don't think you should do this.
Don't use a sweepline algorithm
However, while sweep-line algorithms are nice in theory, implementing them in a robust and efficient manner turns out to be quite difficult in practice. I think this goes doubly so for the Bentley-Ottman algorithm. Therefore, in the field of algorithm engineering, which concerns itself with implementing algorithmic ideas on a computer, (randomized) incremental construction methods are usually preferred. These methods are much easier to make robust and are dynamic (support modifications efficiently) by default2. The (expected) running time is also often not so bad in theory, and can beat the theoretically superior algorithm in practice. (if someone managed to implement the other algorithm effectively, that is).
Use random incremental construction
I recommend the algorithm by Karavelas (described in this conference paper ). It computes a line segment Voronoi diagram in $O((n+m)\log^2 n)$ expected time, together with a hierarchical structure that supports nearest neighbor queries in $O(\log^2 n)$ expected time. (Here, $n$ is number of segments, and $m$ the number of points)
This algorithm is implemented in the CGAL library, see this manual page for the details.

1: Formally, this is only a proper generalisation of a Voronoi diagram if the line segments are disjoint, because if the nearest point is point shared by two segments, we cannot uniquely determine its cell. If these line segments form the embedding of a planar graph, they only intersect at the end-points. In this case, we can often get away with shrinking the segments a tiny bit s.t. the endpoints are now disjoint. Another option is to consider the open segments and their endpoints as 3 separate objects, and make a Voronoi diagram of those.
2: More precisely, insertion is already implemented, and deletion is usually not too hard to add.


Time complexity of euler totient function Code for finding $\phi$(n) is

int phi(int n)
    {
        int result = n;   // Initialize result as n

        // Consider all prime factors of n and subtract their
        // multiples from result
        for (int p=2; p*p<=n; ++p)
        {
            // Check if p is a prime factor.
            if (n % p == 0)
            {
                // If yes, then update n and result
                while (n % p == 0)
                    n /= p;
                result -= result / p;
            }
        }

        // If n has a prime factor greater than sqrt(n)
        // (There can be at-most one such prime factor)
        if (n > 1)
            result -= result / n;
        return result;
    }

I don't understand how is the overall complexity $O(\sqrt{n}) $.

From the code, I see that the outer loop runs for $O(\sqrt{n}) $ time but I am not sure of how to include the time complexity of the inner loop for finding the overall complexity.

If we have n=$128$, then outer loop runs for $O(\sqrt{n}) $ time and inner loop for $O(log_2 n)$, so overall complexity is $O(\sqrt{n}) $  +  $O(log_2 n)$ which is  $O(\sqrt{n}) $.

I don't know how to extend this for general case of $n=P1^{a1}*P2^{a2}*P3^{a3}*..Pn^{an}$

The cost inner loop if $n$ is equal to $P_1^{a_1}P_2^{a_2}\cdots P_k^{a_k}$, should be run in $\log_{P_1}n + \log_{P_2}n + \cdots + \log_{P_k}n$ totaly which is $O(k\log(n))$.Notice that, these computation is computed over the outer loop and summation of all iterations of the outer loop.

To more scrutinizing, as the maximum asymptotic number of primes less than $x$ is $\frac{x}{\log x}$, size of $k$ would be $O(\frac{\sqrt{n}}{\log\sqrt{n}})$. Hence, The complexity of the problem would be:
$$O(\sqrt{n} + k\log(n))=O(\sqrt{n} + \frac{\sqrt{n}}{\log\sqrt{n}}\log(n)) = O(\sqrt{n}+\frac{\sqrt{n}}{2})=O(\sqrt{n})$$


Given n drinks, find optimum way to spend money if for each drink the price and the expiration date is given Let's say we are given $n$ types of drinks, integer $m$ representing the budget we have and integer $d$ representing the cost of delivery when we order some drinks. For each of the $n$ drinks we are given $P_i \text{ the price of i-th drink and } E_i - \text{expire date}$. For example $(3, 2)$ is representing drink with price $3$ for one bottle and the second number means that this drink can be used at most $2$ days after we buy it. One cannot drink drinks that have expired date of usage and one must drink exactly once per day.

We can order as many drinks as we want from each type, but each time we order we are paying $d$ dollars for delivery. Notice that the delivery doesn't matter in the day, so we can buy drink with exprite date $2$ and used it either today, tomorrow, or the day after tomorrow.

We want to maximize the number of drinks we will buy and drink.

I think that this problem can be solved with greedy strategy, but I'm not able to find anything that can lead to correct result and good time complexity.

Here are some things that I got so far:

We don't want to buy things that will be expired, so from each drink with price $P_i$ we will spend at most $P_i \cdot(E_i + 1)$

Because we may have big budget, it is good to find one way of buying drinks and use it couple times, until we don't run out of money from the budget.

We will first buy the cheaper drinks and for the more expensive ones we should decide should we make a new order, or buy some drinks from the next type.

I didn't got anything that lead to correct strategy, so please share some of your ideas.

It’s not very difficult really, assuming we only care about the cost and don’t have any preferences for drinks.

If we want to make a single order that lasts for n days as cheap as possible, we order the cheapest drink with expiry k, for each 0 <= k < n. That supply costs the cost of the drinks plus d. We can calculate this cost for 1 <= n <= E+1, where E is the longest expiry of any drink.

If we want drinks for N days, we make 1 or more orders to minimise the total cost. We may assume the orders are ordered by size in descending order (and if we find the best sequence of orders with this restriction, we can rearrange it any way we like). Finding the best orders is now a simple dynamic programming problem.

If you are looking for something complicated, it’s not needed.


social network analysis - relations between people with weights I asked this question on datascience.stackexchange but they directed me here.
I have a social network represented as a set of people S and individual weights for each of person (weight is the cost of person).
I also have defined relationships between these people (whether people know each other or not).
I must find such a subset D, such that every person in this subset either belongs to the set S or knows someone from the set S directly.
There will be a lot of such subsets.
I want the subset whose sum of weights of people is the smallest.
Let's see example:
D = {(John(7), Adam(15), Viktor(6), Bob(2)} and connections are John - Adam - Viktor - Bob. Solutions are Adam,Bob(17) OR John,Victor(13) OR Adam,Victor(21) OR John,Bob(9). The best is the last one - John,Bob(9).
I thought to create a directed graph where:

Each vertex represents person
Each vertex has a weight assigned to it
Edges between vertices indicate whether the people know each other or not

I imagine this as a minimum spanning tree on directed graphs problem. I found Chu-Liu/Edmond's algorithm, I know that this algorithm works for edge-weighted graphs and I have vertices-weighted, so I just set the edge weights to what are the weights of the vertices at the end of the edge. But this is not optimal solution. I don't need direct connections between people in the set D.
So after I have result from that algorithm, I can apply on it some greedy algorithm, which will go recursively over each element and check how removing it from the subset D will affect the structure - when the sum of the weights will be minimal and will ensure that no element falls out of set D (check below).
Refer to an example, my MST result will be John,Adam,Victor,Bob(27). Best solution is John,Bob(9). Interesting bad solution is Viktor,Bob(8) - the sum is minimal, unfortunately John will fall out of the D subset.
Also I assume that:

cost of a person doesn't correlate with their degree in the network (numbers of
acquaintances)
the maximum number of people and acquaintances (vertices and edges) is about 400

Is my way to solve this problem is good? Do you suggest any other solutions for that?

First a few comments/questions about your approach:

Why do you think your problem has anything to do with minimum spanning trees? I fail to see the connection.
Why is your graph directed when the original problem seems to state that the "know eachother" relation is symmetric? (if A knows B then B knows A)
For your "greedy post-processing" can you do better than looking at all possible  subsets of D? In other words, how does your MST help you compute the correct subset?

Then to answer your question:
If I understood you correctly, the problem you want to solve is a weighted version of dominating set. It is NP-Hard and thus unlikely to be solvable efficiently in the worst case when the number of people increases.
By googling "minimum weight dominating set" you will however find approximation algorithms, heuristics or "practically efficient" algorithms which might do the trick if the number of people in S is not too large (or the specific instance happens to be nice enough). I'm not sure how well they would perform for your considered graph size.
Alternatively, if the number of people in S is really not large (say fewer than 25) then you might consider simply brute-forcing through every possible subset of S.


Provide a polynomial time algorithm that decides whether or not the language recognized by some input DFA consists entirely of palindromes Everything needed to know is in the question statement. I believe that the DFA has to be acyclic (meaning its language is finite), which can be checked in polynomial time. However, finding all paths from the start state to an accept state can run in exponential time in worst-case.

I will give a general algorithm going through intermediate steps that can be implemented in polynomial time, each. Yet, I will not dive into the details of how to implement each step. The solution I'm suggesting may not be optimal, yet it is easy to understand. Essentially, we're going to rely on basic properties of Pushdown automata (PDAs, for short).
Let $\mathcal{A}$ be a given DFA over the alphabet $\Sigma$, and consider the language $PAL\subseteq \Sigma^*$ of the palindrome words. We need to decide whether $L(\mathcal{A})\subseteq PAL$ in polynomial time. Note that $L(\mathcal{A})\subseteq PAL$ iff $L(\mathcal{A})\cap \overline{PAL} = \emptyset$. So we need to decide whether the language $L(\mathcal{A})\cap \overline{PAL}$ is empty, and we do it as follows:
1- Construct a PDA $\mathcal{B}$ for $\overline{PAL}$: this is a well known exercise.
2- Construct a PDA $\mathcal{C}$ for $L(\mathcal{A})\cap \overline{PAL}$: this is also known, and can be done in polynomial time by a product construction of $\mathcal{A}$ and $\mathcal{B}$ (for example, see here).
3- Finally, check whether the language of the PDA $\mathcal{C}$ is empty. This also can be done in polynomial time (see here, or here).


Frame Pointers in Assembler I am currently learning assembly programming on wombat 4, I am looking at Frame pointers. I understand exactly what a frame pointer is: it is a register and are used to access parameters on a stack. But i'm confused on how they affect the program counter and why they are preferred over normal registers.

Could some one explain, please.

As the stack pointer may change while a function is executed, access to the stack is less confusing with a static frame pointer, that is set upon the entry to the function, so relative addressing becomes simpler.

On reason for using the stack to store parameters is that there is usually more memory available than registers. What would you do with a function g(a,b,c,d,e,f) where you have enough registers free to store a–e, but non for f? You would put f on the stack. As the size of the stack is only limited by the available memory using the stack still works for functions with even more parameters.

Modern compilers typically have a flag that controls whether the use of registers for parameter passing is allowed or not.


Removing recursion from a function with multiple params I am given the following function as a brain teaser:

def t(x, y, z):
    if x <= z:
        return y
    else:
        return t(t(x  - 1 , y  , z ) , t(y  - 1 , z  , x ) , t (z  - 1 , x  , y ))

the task is to remove the recursion in the else-branch. the only allowed expressions are of type arithmetic (+,-,*,/,%), logical (&&,||,!),
relational (<,<=,==,>=,>,!=) and if-else.

My first approach was to order the input in lexicographical order and trying to deduce a relationship which seemed to look like like this initially:

else:
    if y > x
        return x
    else:
        return z

but that does not work, a counterexample is t(20, 7, 18)=8. So the underlying relationship seems to be a bit more complex. I have also tried to formally infer the solution by differentiating the cases for the '>'-relation between the variables but I did not get far with that either.

Here is an equivalent way to calculate $t(x,y,z)$.

We distinguish between three cases:

$x \leq z$: the answer is $y$.
$x = z + 1$: the answer is $z$ if $y \leq x$, and $x$ otherwise.
$x-z \geq 2$: the answer is $z$ (if $x-z$ is odd) or $\min(y+1,z)$ (if $x-z$ is even) if $y \leq x+1$, and $x$ (if $y-x$ is even) or $z+1$ (if $y-x$ is odd) otherwise.

You should be able to prove this characterization by induction. The second case is identical to the third case, except that the condition $y \leq x$ is replaced by the condition $y \leq x+1$.


What is the time complexity of enqueue and dequeue of a queue implemented with a singly linked list? I’m trying to understand the time complexity of a queue implemented with a linked list data structure. My book says that we can the implement a queue in O(1) time by:

enqueueing at the back
dequeueing at the head

and it also says

  Note that although adding an element to the tail is constant time,
  removing an element from the tail is O(n) as we have to find the new
  tail

I know that adding a new node to my queue at the head (enqueue) takes O(1) since I have the head pointer. Similarly, removing a node at the head (dequeue) will take O(1) as well. But I don’t understand why adding an element at the back (enqueue) takes O(1), while removing it (dequeue) takes O(n). It would make more sense to me if enqueueing at the back took O(n) rather than O(1), since in both cases (adding/removing at the back) would need to find the tail pointer and therefore it would need to traverse the entire list.

Enqueueing

You don't need to traverse the entire list to find the new tail, you just need to add a new node where the current tail points to and set that node as the new tail.

Pseudocode (assuming that head != null and tail != null):

function enqueue(value) {
    node = new Node(value)     // O(1)
    tail.next = node           // O(1)
    tail = node                // O(1)
    size++                     // O(1)
}

From which we can conclude that the time complexity is $O(1)$.

Dequeueing

For dequeueing, we only need to set the next node of the current head as the new head and return the value of the old head.

Note: Don't forget that if the new head is set to null, the tail should be set to null as well:

Pseudocode (assuming that head != null and tail != null):

function dequeue() {
    value = head.value         // O(1)
    head = head.next           // O(1)
    size--                     // O(1)

    if (head == null) {        // O(1)
        tail = null            // O(1)
    }

    return value               // O(1)
}

All these operations have $O(1)$ time complexity, which makes the time complexity of the dequeue function $O(1)$ as well.

Searching

Searching for a value is done by traversing through all the items, starting from the head. In the worst case scenario, you would need to traverse the entire queue, which makes the worst-case time complexity $O(n)$.

For example, if you want to remove the tail, the time complexity would be $O(n)$. This is because you would need to find the new tail for the queue and since the tail does not have access to the previous element in a singly linked list, you would need to search the entire queue for the new tail.

Pseudocode (assuming that head != null and tail != null):

function removeLast() {

    // Edge case when there is only 1 element in the queue.
    if (head == tail) {                   // O(1)
        value = head.value                // O(1)
        head = null                       // O(1)
        tail = null                       // O(1)

        return value                      // O(1)
    }

    // Searching for the new tail.
    newTail = head                        // O(1)
    while (newTail.next != tail) {        // O(n)
        newTail = newTail.next            // O(1)
    }

    value = tail.value                    // O(1)
    newTail.next = null                   // O(1)
    tail = newTail                        // O(1)

    return tail                           // O(1)
}

From which can be seen that the time complexity is indeed $O(n)$.


Is it known that $AC^1 \subseteq L$? A good exercise is to show $NC^1 \subseteq L$. (According to the complexity zoo page this was first shown by Borodin, 1977.) Although the details must be checked, the proof is simple: take the $NC^1$ circuit and do depth-first-search on the output gate of the circuit. Recursively evaluating the gates in the circuit works because the depth of recursion never goes beyond the depth of the circuit, which is $\log n$.

My question: doesn't the same argument show that $AC^1 \subseteq L$? In this case, with unbounded fan-in, we have to modify the argument slightly, to make sure we are only storing, at each gate, a pointer to the current input gate we are recursing on, and the result (AND or OR) of all input gates up to this point. But it should still be $\log n$.

There must be something wrong with this argument, since I don't see $AC^1 \subseteq L$ referenced anywhere, and the Complexity Zoology inclusion diagram does not list $AC^1$ as a subset of $L$ :( So, what is the error in my thinking?

Matrix powering shows that directed reachability is in $\mathsf{AC^1}$, and so $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{AC^1}$. In more detail, suppose that $A$ is the adjacency matrix of a directed graph $G$, with self-loops on all vertices. The matrix $B_{ij} = \bigvee_k A_{ik} \land A_{kj}$, which can be computed in $\mathsf{AC^0}$, is the adjacency matrix of $G^2$. In other words, $B_{ij} = 1$ iff there is a path of length at most 2 from $i$ to $j$ in $G$. Iterating this construction $\log n$ times, we obtain an $\mathsf{AC^1}$ circuit computing the adjacency matrix of $G$, that is, which vertex is reachable from which vertex.

What goes wrong when using DFS to evaluate $\mathsf{AC^1}$ circuits? The same approach works, only it uses $\log^2 n$ space rather than $\log n$ space. The reason is that at each level, you need $\log n$ space to store which child you are currently in. Multiplied by the number of levels, we obtain $\log^2 n$.


What if block sizes are not equal among caches? In all the books, packets of slides and similar I read, cache miss is always explained by assuming that blocks of different caches (or cache and RAM) are always of the same size. It's pretty clear how it's works in this case but the question is: what if block dimensions are not equal among caches?

For example, assuming a L1 cache of 8KB and 16B blocks (that implies 2^9 blocks) and a L2 cache of 512KB with 32B block (that implies 2^14 blocks). Assuming that a load have to be executed, i.e. LD R1,(0x0000AFAF) and suppose that there is a cache L1 miss and a cache L2 hit, what happens? What I mean is that i know that a block containing that addressed byte would be stored in L1 cache and i know where. The problem is what i have to save. I mean, have i to save half block of L2 cache (from 0x0000AFA0 to 0x0000AFAF) in a block of L1 cache or have i to save a block of L2 cache (from 0x0000AFA0 to 0x0000AFBf) in two block of L1 cache? Would be the same if i had cache + RAM instead?

To begin with, block sizes are usually equal across all levels of the cache hierarchy. I would like to see if someone has an example of a commercial architecture where is is not true. There are multiple reasons for this, all of which involve circuit complexity

Now, to answer your question, one could do either. When the processor requests a SP float (4 bytes), only 4 of the 16 (in your example) bytes from the block of the L1 are sent towards the pipeline. The same logic that selects this subset of bytes can be used to select the subset of 16 bytes (in your example) from the incoming block of 32 bytes.

Alternatively, you could over-write the neighboring block in L1 with data from the block of 32 bytes because spatial locality would imply you are likely to require this data soon.


Is every AVL tree a BST or just BT? I was going through the concepts of AVL tree and came across the definition of AVL tree from the wiki.

  In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree

even most of the definition claims that AVL tree is BST, but is every AVL tree needs to be BST can't it be just BT?

In my point of view, AVL follows an algorithm that balances the Binary Tree, as BST is the subset of the binary tree, then this balancing algorithm can be applied on it.

is there anything that I am missing? Any contradictory example will be highly appreciated.

Yes every AVL tree is a BST

also note that every binary search tree itself is a binary tree (binary tree is basically a tree that each node has at most two child)  so therefore every AVL is a binary tree as well.

AVL tree is just a binary search tree that tries to do rotations when its needed (when the tree becomes unbalanced) in order to stay balanced, and therefore the search time would be O(logn)

the reason behind using AVL instead of BST is to make sure the search time is O(logn) because if we use BST and insert the values in a decreasing or increasing order then the BST would be one sided and the search time will be O(n), but if we do that using AVL then the tree will balance itself using rotations.

i suggest you to read the definitions of all of them so you can understand better.


Shuffle an array based on some rules I have a set of images. The length is variable. It could be anything up to about 30 images. Each image can have up to 10 tags. Images may share some, all or none of their tags. I need to select a random 5 from this set of images. This selection should follow the following rules in order of high priority to low:

Two images with the exact same tag(s) MUST NOT appear next to each other unless no other option is available.
Which two images appear next to each other should be decided by a weight system that favours images that share less tags or none at all. The more different tags two images have, the more likely they should be to appear side by side and vice versa.
Rule 2 also applies to the entire set of 5, but to a lesser degree. It means we prefer the selected 5 to share as few tags with one another as possible, but this should not take priority over rule 1 and 2.
(Optional) When selected images share tags, the more tags they share, the further apart they should be from each other.
(Optional) As a bonus, it would be nice not to sacrifice randomness because of rule 3 and 4, but this is more of a nice-to-have and is not necessary.

I'm looking for an algorithm that can help me solve the above problem. This is part of a real-world application UI and as a result, it'd be best if it doesn't take more than a second to calculate the set of 5. Anything longer than a second is bad. Even a second is too long.

If anyone has a solution that takes up to a minute or so, I might be able to do some pre-processing on the data so I am still open to it.

I would like you to note that the selection cannot be fully random.. Assume there are 10 total images.

5 have the same tags
5 have a single but unique tag

Then the algorithm will Always choose the same 5 images (And will Always skip the other 5 images).

Luckily there's an algorithm that can help you easily. Note that this algorithm skips points 4/5 (which you claim are optional).

Foreach image => sort its tags alphabetically

Find the longest tag

Postfix the same letter to all the tags in order to make them the same lenght

In example if you have the tags cherry,optimization,google those tags are transformed into

cherryXXXXXX
optimization
googleXXXXXX

Foreach image, make a string that is made by concatenation of all its tags. Then sort those strings alphabetically.

In Example:

Image1 - tags: B, EE, A
Image2 - tags: A, C
Image2 - tags: Z

The final strings would be

AXBXEE
AXCX
ZX

Put your strings in a doubly linked, linkedlist, select a random element, then skip "some elements" (in example if you have 300 strings, you can select the first random and then skip 40-60 strings ) and take another element.

This algorithm is not complex, and not cheap, but is a good start point, note that your algorithm have to be a euristic-based (or greedy) algorithm because I fear your problem has a big computational complexity (still checking that, I'll update later this answer).

An alternative algorithm complexity (n number of images)

Assume the number of tags is limite to 10.

set all scores to 0
foreach img in images
    foreach img2 in images
       img.score -= TagsInCommon(img,img2)

for (int i = 0; i<5; i++)
{
    images.SortBy( x => x.score);
    img = images.RemoveFirst(); // pick image with highest score
    foreach img in images // (we have removed the first image here)
       foreach img2 in images
           img.score -= TagsInCommon(img,img2) //adapt score slightly
}

The above algorithm has a complexity of roughly

O(n^2 + nlogn + n)

where n is number of images (I did not check complexity ineherent in string lenghts, number of tags etc.).

This algorithm basically is another algorithm with a greedy approach, image with unique tags will be the first selected images, while images that are heavily tagged will be putted to the end of the list (and possibly are never sorted out). Plus we are adapting the score during execution to remove tags that we have already drawed.

A better alternative would be (instead of removing Always the first element) to select a random element with a distribution that favours the elements with higher score (but at same time do not forbid to draw elements with low score).

This algorithm will probably will take less of a second even with something like 100 thousand images.

A distribution like the following would suffice:


How/when is calculus used in Computer Science? Many computer science programs require two or three calculus classes.

I'm wondering, how and when is calculus used in computer science? The CS content of a degree in computer science tends to focus on algorithms, operating systems, data structures, artificial intelligence, software engineering, etc. Are there times when Calculus is useful in these or other areas of Computer Science?

I can think of a few courses that would need Calculus, directly. I have used bold face for the usually obligatory disciplines for a Computer Science degree, and italics for the usually optional ones.

Computer Graphics/Image Processing, and here you will also need Analytic Geometry and Linear Algebra, heavily!  If you go down this path, you may also want to study some Differential Geometry (which has multivariate Calculus as a minimum prerequisite). But you'll need Calculus here even for very basic things: try searching for "Fourier Transform" or "Wavelets", for example -- these are two very fundamental tools for people working with images.
Optimization, non-linear mostly, where multivariate Calculus is the fundamental language used to develop everything.  But even linear optimization benefits from Calculus (the derivative of the objective function is absolutely important)
Probability/Statistics. These cannot be seriously studied without multivariate Calculus.
Machine Learning, which makes heavy use of Statistics (and consequently, multivariate Calculus)
Data Science and related subjects, which also use lots of Statistics;
Robotics, where you will need to model physical movements of a robot, so you will need to know partial derivatives and gradients.
Discrete Math and Combinatorics (yes!, you may need Calculus for discrete counting!) -- if you get serious enough about generating functions, you'll need to know how to integrate and derivate certain formulas. And that is useful for Analysis of Algorithms (see the book by Sedgewick and Flajolet, "Analysis of Algorithms"). Similarly, Taylor Series and calculus can be useful in solving certain kinds of recurrence relations, which are used in algorithm analysis.
Analysis of Algorithms, where you use the notion of limit right from the start (see Landau notation, "little $o$" -- it's defined using a limit)

There may be others -- this is just off the top of my head.

And, besides that, one benefits indirectly from a Calculus course by   learning how to reason and explain arguments with technical rigor. This is more valuable than students usually think.

Finally -- you will need Calculus in order to, well, interact with people from other Exact Sciences and Engineering. And it's not uncommon that a Computer Scientist needs to not only talk but also work together with a Physicist or an Engineer.


What are the drawbacks of using an algorithm that is not backwards stable? (This question might be legitimately crossposted to stackoverflow or mathoverflow or programming StackExchanges.)

Preface

I'm reading this paper on solving linear systems of equations Ax = b using an explicit inverse (held by conventional wisdom as a big no-no): Druinsky & Toledo, "How accurate is inv(A)*b?", http://arxiv.org/abs/1201.6035

It asserts that in non-pathological cases, calculating a solution to Ax=b via inv(A)*b using the explicit inverse of a matrix produces solutions that are as accurate and as stable as preferred methods such as via LU factorization. It goes on to describe exactly which situations using "inv" might be bad (technically, when the right-hand side, b, is nearly orthogonal to the subspace spanned by left-singular vectors of A with low singular values). Even in these cases, the paper asserts, the solutions of inv(A)*b are as accurate as preferred methods, they're just not backwards stable.

Question

My question is: what are the specific drawbacks of using an algorithm that isn't guaranteed to be backwards stable? If all I wanted was some solutions to Ax=b, and I was guaranteed accurate results, does it matter that the solutions aren't backwards stable? Is there any specific examples of when it's ok to use an accurate but backwards-unstable algorithm?

Furthermore

My experimentation in Matlab/Octave shows me that the difference between a backwards-unstable and -stable algorithm is that slight perturbations to the solution result in bigger errors when going back through the linear system:

norm(A * (inv(A) * b) - b)

is much larger than

norm(A * (A \ b) - b)

for a "bad" b (nearly orthogonal to the subspace of left-singular vectors with low singular values), where \ solves linear systems using Gaussian elimination (http://www.mathworks.com/help/matlab/ref/mldivide.html). The solutions themselves have the same accuracy, i.e., norm(A\b - true_x) is about the same as norm(inv(A)*b - true_x).

I can imagine that in the case that

I only cared about getting a solution to Ax=b and
knew I would never propagate the solution back through A,

could I justify using inv(A) when I didn't want to bother checking that b isn't "bad", i.e., without ensuring that the solution was backwards-stable. To me, this doesn't seem worth it, even without the speed and convenience advantages of using LU or Cholesky or QR decompositions.

Sivan Toledo responded to my query with the following:

  In general, the significance and the broad-context meaning of
  mathematical results is a matter of opinion and debate, so perhaps not
  every researcher would agree to our explanation below.

  In most of the literature, backward stability is a technical and/or
  analytic tool that makes it relatively easy to prove that an algorithm
  produces accurate results (or to bound the inaccuracy). In these
  contexts, the user of the numerical method worries about accuracy, not
  about backward stability, and the numerical analyst uses backward
  stability just as a mechanism to prove the bound that the user cares
  about.

  (The analysis in our paper proves accuracy without relying directly on
  backward stability, but this is atypical.)

  When an algorithm is backward stable, the user gets not only a bound
  on the magnitude of the error, but also an estimate of its direction;
  it lies in the direction of right singular vectors that correspond to
  small singular values (for the case of solving linear equations). In
  many cases this is completely meaningless to the user.

  Backward stability may be meaningful to the end user if the parameters
  of the problem (say the coefficients of a linear equation) are only
  known approximately, say because they are measured or estimated using
  some limited-accuracy physical instrument. In some of these cases it
  may be good for the user to know that the output she/he got is an
  exact solution to a nearby problem.

I'd still like to better understand theoretically what the drawbacks of using inv(A)*b are when b is "bad". That is, if the solution using inv is as accurate as with a "better" algorithm, what really matters. (This is hinted at computationally in my question: the projection matrix A * inv(A' * A) * A' is at least unreliable.)


How to balance doing a literature review and just solving the problem yourself I work for a company that has several projects involving computer vision.  The literature rarely has papers on the exact problems we are solving.   Furthermore, the state of the art in much of computer vision is often not reproducible or not ready for actual applications.  Furthermore, the rate at which new papers come out in the areas we are interested in would make it very time consuming to digest most, let alone all of them.

On the other hand, we often get stuck and would like to get answers or at least inspiration from existing work.

Our goal in the end is to get to solutions as fast as possible.  Does anyone have any guidance on how to balance time spent reading vs doing?

Before trying to solve the problem yourself, it is always a good idea to search the literature, to see if somebody else has already solved it, or at least has worked on something similar.  This is especially true in computer vision.  A good strategy is to allocate some reasonable amount of time to read papers. If you find nothing useful in that time, then you give up and try to come up with your own solution.

Yes the number of computer vision papers published every year is staggering. So a good strategy is to try to keep up with a few top conferences, such as CVPR, ICCV, ECCV, and BMVC, and a few top journals, such as PAMI and IJCV.

Also, it is good to find researchers and research groups who are working in your particular area of computer vision, and follow their progress, and the papers which cite them.


Do Kruskal's and Prim's algorithms yield the same minimum spanning tree? Assuming the edges are undirected, have unique weight, and no negative paths, do these algorithms produce the same Minimum Spanning Trees?

Found this which states that if all the conditions I mentioned above are met, a graph necessarily has a unique MST. Therefore, in terms of my question, Kruskal's and Prim's algorithms necessarily produce the same result.


Can an intersection of two context-free languages be an undecidable language? I'm trying to prove that

$\exists L_1, L_2 : L_1$ and $L_2$ are context-free languages $\land\;L_1 \cap L_2 = L_3$ is an undecidable language.

I know that context-free languages are not closed under intersection.

This means that I can produce an $L_3$, which is undecidable.

An example would be $L_1 = \{a^n | n \in \mathbb{N}\} \cap L_2 = \{0\} = \emptyset$.

Is this a correct proof?
If not, how can I prove this theorem?
Is the empty language decidable?

Context-free languages are decidable, and decidable languages are
closed under intersection.

So, though the intersection of two CF languages may not be CF, it is decidable.

Remarks on your example:

$\emptyset=\{\}\neq$ $\{0\}$
$L_1\cap\emptyset=\emptyset$  which is context-free.
You cannot prove your claim, because it is wrong
the empty language is decidable: the answer is always "no, this string is not in the empty set".


Define the following problem as a language and prove that it is undecidable with a reduction from the halting problem. ...Knowing whether a Turing machine will ever output your name on the tape. The language is the set of all TMs that print your name. Reduce from HALT TM.

I had this problem on my exam. From my understanding, the halting problem involves a program with some input, and that program will either output yes or no as output when comparing the input to the desired value. Then there's another program that must determine if the original program will ever halt based on the input given to it.

Thing is, I'm not sure if I understand the entire concept here. It's undecidable because we are unable to write a program that can determine if a program will always halt or stay in an infinite loop? Since it will always output as a "yes, it halted" even though the original program either halted or remained in an infinite loop.

So, I'm pretty new to all this, so bare with me. If the original question was asking me to "reduce" from the halting TM, do I apply the same principles? Or am I working out the problem differently? What is a reduction exactly, and what was I supposed to do here?

Since you seem to want only a hint rather than a full solution, here is my attempt:

Undecidability of the Halting problem is one of the most famous impossibility results. It is not the most powerful one in the series (consider Rice's theorem) but it is a relatively simple in layman's terms and IMHO pretty impressive (in a bad way). The undecidability  of the halting problem means that no matter which algorithm you try for the halting problem, it will fail on some inputs. It does not say that you can't predict if the program will halt for each (program, input data) pair, for example there are some very predictable programs. But it says that for every deciding program there will be some bad pair (possibly different for different programs, but even if you "combine" many such deciding programs, there still will be some bad cases).

Reduction is a general concept in math with several overlapping meanings. Here is one related famous joke about mathematicians:

An engineer and a mathematician were shown into a kitchen, given an empty pan, and told to boil a pint of water. They both filled the pan with water, put it on the stove, and boiled it.
The next day they were shown into the kitchen again, but this time given a pan full of water, and told to boil a pint of water. The engineer took the pan, put it on the stove, and boiled it. The mathematician took the pan and emptied it, thereby reducing it to a previously solved problem.

On a more serious note, reduction to the Halting problem is an argument that shows that a perfect anti-virus is impossible: the virus potentially can do its harm at any time during its whole runtime. So if the antivirus can catch all the viruses, it has to be able to solve the halting problem because I can put my virus "at the end" of any other program which the antivirus has to analyze first.
If you want a similar but I bit more formal argument take a look at wiki reduction of the Rice's theorem to the Halting problem
Generally in the CS-world reduction is mostly used in two ways:

To prove that some problem is undecidable by reducing it to some other well-known undecidable problem (and the Halting problem is often used here). In other words, if we could solve the problem X, we also must be able to solve the problem A which is known to be undecidable so X must be undecidable as well.

To prove some boundaries on complexity of some problem. For example, problem X is NP-complete because here is how to transform (reduce) an arbitrary input for a known NP-complete problem A into an input of the problem X and then how to transform the answer back.


Numerical Approximation in Java I am trying to solve an equation which I believe cannot be done analytically, but can use a numerical approximation to get a result. The equation is:
$$\frac{2*\sqrt{\pi}*h*s*e^{m^{2}/(2*s^2)}}{\sqrt{2}} = a$$
where $h, m,$ and $a$ are given constants. This is for a project that I'm writing in Java, and it would be infeasible to grab the solution output from another program such as Matlab, Mathematica, or some other scientific computing language for a couple reasons, one of which is that I will have to solve this equation hundreds of times with different values. Basically I am wondering if anybody knows of a library I can easily import and use for this kind of problem, and to possibly spell out how I would go about doing that. So far I have been looking through math libraries such as Apache Commons Math but cannot find out if they are appropriate. Thanks!

You are asking how to solve $e^{ax^2}=b$ for $x$, given constants $a,b$.  The solution is $x=\sqrt{\frac{1}{a} \log b}$, which can be computed (approximately) using standard algorithms for computing the log and the square root.

In particular, your specific equation has the solution

$$m = \sqrt{2s^2 \log (a/(\sqrt{2\pi} hs))}.$$

You can verify the correctness of this solution by plugging into the equation and verifying it works.


Why does paging not have external fragmentation? I have read that paging does not suffer from external fragmentation as the frames and the pages are all of the equal sizes, but when we store a last level page table in a frame at that time it may not fully occupy the frame. Similarly, if n such page tables are stored, that does not occupy the frames entirely, then there can be a case where all the gaps exceed a page size. Then there should be external fragmentation, right? So why is it said that paging does not have external fragmentation?

The details depend on the processor architecture, but the principle is the same everywhere. All page tables of a given type at a given level have the same size. When all memory blocks have the same size, there is no fragmentation: a memory block is allocated starts at an offset which is a multiple of the block size, so the size of any hole is a multiple of the block size. If a gap opens in the page table, the operating system can use this gap the next time it needs to allocate a page table.

Furthermore the size of a page table pretty much always divides the size of a page — both are powers of two. So a page contains a whole number of page tables with no leftover space. This means that the operating system can allocate pages for page tables and no table spreads over multiple pages, so there's no need for the page tables to be consecutive and therefore there's no fragmentation of the address space for the page tables themselves.


Nullable nonterminals and recursion I have two questions regarding nullable nonterminals in a grammar. Often a simple algorithm is described to find nullable nonterminals:

  Basis: if $A \rightarrow \epsilon$ is a production, $A$ is nullable.
  Induction: if $A \rightarrow X_1X_2\ldots X_n$ is a production, and $X_1, X_2, \ldots, X_n$ are all nullable, then $A$ is nullable.

Intuitively, this algorithm seems correct. But I don't see how it could properly show $B$ to be nullable in the following grammar:

$$A \rightarrow a$$
$$A \rightarrow \epsilon$$
$$B \rightarrow B A$$

How does the algorithm deal with these recursive productions that are nullable? If not, what changes must be made to make it correct?

My second question is whether the following grammar is nullable, or whether it's even a valid context-free grammar at all.

$$S \rightarrow S$$

A nonterminal $X$ is nullable if there is some derivation $X \to^* \epsilon$. It is clear that all non-terminals found by your algorithm are nullable (you can prove this by induction). On the other hand, if $X$ is nullable then take a derivation tree for the derivation, and prove by induction on the depth that all non-terminals on the way are recognized as nullable by this algorithm. This is why the algorithm is correct.

In your first example, $B$ is not nullable. In fact, you can't generate any string from $B$. The same is the case for your second example $S\to S$, where again the grammar generates no strings.


Cache read controller Does the cpu interface with a memory controller to read the cache? What happens when data is not in the cache, a cache miss, does it automatically fetch the data?

Information about on die structures are scarce for the intel CPUs. You can look at https://en.wikichip.org/wiki/amd/microarchitectures/zen#Memory_Controller for information on AMD CPUs. Especially the following images:

You have the actual die seen under a microscope for the Zen microarchitecture. You clearly see the L3 and L2 controllers. There is one L2 cache per core while there is a shared big L3 cache in the middle.


How can I implement a data structure which calculates the number of nested intervals in sub-linear time? Is there a data structure which can maintain a list of intervals and the following operations?
insert(l, r): Inserts an interval [l, r] into the list
query(l, r): Return the number of intervals in the list which are completely nested in [l, r]

I need the data structure to handle inserting and querying without brute force (which would take linear time).
I saw this algorithm for counting the number of nested intervals for each interval here:
https://stackoverflow.com/questions/12946497/sub-on2-algorithm-for-counting-nested-intervals
but it appears to only calculate the answer for a static array of intervals.

Expanding on Dmitry's comment, you can maintain a balanced tree with the left endpoints of the intervals as the keys, and at each node store a balanced tree with the right endpoints as keys, and at each node of each of those trees store a count of intervals.
This requires $O(n\log n)$ space. Lookups are $O(\log^2 n)$. Insertions are tricky because when rebalancing the outer tree you have to rebuild the inner trees, but I think it can be made amortized polylog(n) if you rebalance sufficiently rarely, using a scapegoat tree for example.
If you know that the endpoints will belong to a set of size $k$, and you don't mind factors of $\log k$ in the insertion and lookup times, then you could use a radix tree for the outer tree and avoid the rebalancing logic.


How can one find an element in a Merkle tree? How can one find an element in a Merkle tree, as effectively as possible?

Each internal node has a hash value. So I think, first, hash the value to find, and if an internal node has the same value exactly, get its leaf node. But this is correct in 2-depth, not all cases. Because each internal node has a hashed what is concatenation of their child nodes, by the avalanche effect, the concatenated hash value is unexpected.

So I cannot find the value to do hash and compare.

Merkle trees are not designed to support efficient lookup.  The best you can do is search the entire tree (all the leaves) and check each node for a match.  This is $O(n)$ time.

If you want to be able to efficiently look up an item in a Merkle tree, construct a separate "index": i.e., a separate hashtable (or binary search tree) storing the mapping from hash value to position in the tree.


similar language by two DFA then why wrong answer I attempted a mock paper for finite automata .so i was asked to create a DFA which accepts a language in which inputs are a,b and number of b's should be divisible by 3.The first image is my answer  for which i was not given marks .but when i checked the answer of the paper they gave the second image as the correct answer.Both the DFA give the accept the language(number of b divisible by 3),so can any one tell how the second DFA in the second is better than the first one,or where did i go wrong.

First DFA does not accept $\epsilon$ which has 0 number of $b$'s which is divisible by 3 (0 is said to be divisible by 3). So first answer is incorrect, where as second is correct.


2SAT Problem using Implication Graph I was doing a practice question. As you can see below there is an Implication graph. To check whether the problem is satisfiable, I checked whether there were any 'bad loops'. To do so, for each literal/variable in the boolean formula, I see if there is a path from X --->-X and from -X---->X if both exist then a 'bad loop' exists and thus the problem is not satisfiable. I did that and saw that there were no such loops and thus I came to the conclusion that the 2SAT problem was satisfiable. See below:

I realized that option d (The 2SAT problem is satisfiable if a,b,c and d are set to false. I'm struggling to come to this conclusion by looking at the graph. My understanding is that you take all the paths in the graph, and see if you come to a contradiction? Can someone please let me understand how to understand option d being correct.

Thanks in advance!

The method I have come up with is to write out the arcs/edges for each implication and work backwards to derive the 2SAT boolean formula and see if it works. Does anyone know a quicker way? :)

For any variable $X$, if there is a path from $X$ to $\neg X$ then you cannot set $X$ to $True$, since otherwise you would end up with a $True \Rightarrow False$ implication somewhere along the path. For the same reason, if there is a path from $\neg X$ to $X$ you cannot set $X$ to $False$.

Hence, in the first case you must set $X$ to $False$, in the second you must set it to $True$. If there are paths in both directions, as you already know, the formula is not satisfiable.

In your example, there are only paths from $X$ to $\neg X$ for all variables, hence the only assignment that satisfies the instance is the one where all variables are $False$.


Best complexity to find solutions to $x^2+y^2=z^2$ What is the algorithm with the best complexity that finds solutions in a given range to the equation $x^2+y^2=z^2$ ?

The best i could do is to iterate through all $x$ and all $y$ and store $x^2+y^2$ in a hash and then iterate through all possible $z$ and check if $z^2$ is in the hash.

I think you are asking about Pythagorean Triples (the form $x^2+y^2=z^2$ where $x$,$y$ and $z$ are integers).

Euclids Formula is generally thought to be efficient for finding primitive Pythagorean Triples.You can multiply these primitive triples with a constant to get non primitive Pythagorean Triples.

Here are some other methods of finding Pythagorean Triples


How to find the minimal DFA for the language? Design a minimal DFA for the language which contains numbers in the form of binary strings starting with $101_2$ and is divisible by $100_{10}$?

I think the numbers will be 700,1400,2100 ... in the form of binary strings which are starting with $101_2$ and are even divisible by $100_{10}$.

100 is divisible by 25 and 4.

For divisible by 4 - Minimum 3 state DFA is possible For divisible by 25 - Min 25 state DFA is possible.

Hence, for divisible by $100_{10}$ - Minimum 100 states DFA is possible .

So, for starting with $101_2$, I have to add 3 extra states along with one dead state.

So, total states in minimal DFA = 100 + 3 + 1 = 104

Is my approach correct or am I missing something?

Your approach towards estimating the number of states is just fine. however the number of states looks quite intimidating and it may be cumbersome to minimize the DFA later.
 In such cases constructing the automaton through intersection is easier. for example as we know the regular languages are closed under the intersection operation we can devise 3 different automata to accept :
 1. String divisible by 25
 2. String divisible by 4
 3. Strings beginning with 101

And then arrive at the final automaton by taking intersections of the 3 machines.

How this helps?

Many of the states originally present in the different machines gradually become unreachable from the initial state in the final automaton and thus the number of states reduce or the DFA is minimized.


Divide and conquer problem:sequence of integers (with possible repetitions) I was trying to solve this problem.
Let $A[1] . . . , A[n]$ an ordered sequence of integers (with possible repetitions) and let $k$ be any integer. A contiguous subsequence $A[i], A[i + 1], . . . A[j]$ of $A$ is $k$-separated if the difference between every pair of its consecutive elements is at most $k$.
For example, if $A = [1, 3, 3, 4, 4, 4, 5, 7, 8]$, then the contiguous subsequence $3, 3, 4, 4, 4, 5$ is $1$-separated but not $0$-separated.
We would like an algorithm that given $A$ and $k$ as input returns the length of the longest contiguous k-separated subsequence.
Some examples:

Input: $A = [1, 3, 3, \textbf{4, 4, 4}, 5, 7, 8]$, $k = 0$. Output: $3$ (longest contiguous $0$-separated subsequence has been hightligthed)
Input: $A = [1, \textbf{3, 3, 4, 4, 4, 5}, 7, 8]$, $k = 1$. Output: $6$ (longest contiguous $1$-separated subsequence has been hightligthed)

This can be solved in $O(n^2)$ with a nested loop that checks all possible contiguous subsequences but we would like to do
better.
I understand that I need to split my array in 2, but after that I don't know how to find the condition to select first half or second.
How will be the algorithm to find the correct answer? Any help it's welcome.

If you want to use a divide-and-conquer algorithm, you can cut the array $A = [a_1, …, a_n]$ in two arrays by the middle $B = [a_1, …, a_{\frac{n}{2}}]$ and $C = [a_{\frac{n}{2}+1}, …, a_n]$.
Then the longest $k$-separated sequence in $A$ is one of the three following:

the longest $k$-separated sequence in $B$;
the longest $k$-separated sequence in $C$;
the concatenation of the longest $k$-separated sequence in $B$ ending with $a_{\frac{n}{2}}$ with the longest $k$-separated sequence in $C$ beginning with $a_{\frac{n}{2}+1}$, with the condition $a_{\frac{n}{2}+1} - a_{\frac{n}{2}} \leq k$.

Now the first two values can be computed recursively, and the third can be computed easily in time complexity $O(n)$. The complexity of this algorithm verifies $C(n) = 2C\left(\frac{n}{2}\right) + O(n)$, which implies $C(n) = O(n\log n)$.
Without divide-and-conquer, I think there exists a $O(n)$ dynamic programming algorithm:
For $A = [a_1, …, a_n]$ and $i \in [\![1, n]\!]$, define:

$f(i)$: length of the longest $k$-separated sequence in $[a_1, …, a_i]$;
$g(i)$: length of the longest $k$-separated sequence in $[a_1, …, a_i]$ ending with $a_i$.

Then it is easy to see that:

$g(i + 1) = \left\{\begin{array}{rl}1 & \text{if }a_{i+1}-a_i >k\\ 1 + g(i)&\text{otherwise}\end{array}\right.$
$f(i + 1) = \max(f(i), g(i + 1))$

That way, you can easily compute $f(n)$, which is the value you want, in time complexity $O(n)$.


How to find kth largest element in (max) priority queue in O(m) time? Here is my exercise.

  FINDLARGEST(k): return the elements in the heap with key >=k" ... "expand the priority queue (max-heap) so that it supports FINDLARGEST(k) in O(m) time, where m is the number of elements with key>=k.

Can anyone elaborate on this maybe?

I stumbled upon this on the wikipedia entry on min-max heap: "The structure can also be generalized to support other order-statistics operations efficiently, such as find-median, delete-median,[6]find(k) (determine the kth smallest value in the structure) and the operation delete(k) (delete the kth smallest value in the structure), for any fixed value (or set of values) of k. These last two operations can be implemented in constant and logarithmic time, respectively." However, that did not help much.

You can implement FINDLARGEST recursively:

FINDLARGEST(k, vertex) # call with vertex = root
  if value(vertex) < k: exit the function
  output vertex
  FINDLARGEST(k, left-child(vertex))
  FINDLARGEST(k, right-child(vertex))

If there are $m$ vertices whose value is at least $k$, then FINDLARGEST explores at most $3m$ vertices: each eligible vertex together with its two children.


Creating arrays of object of abstract class in statically-typed object-oriented languages In statically-typed object-oriented languages (like Java, C++, C#, ...), suppose I declare an abstract class:

public abstract class myclass1 {
 .................
}

Most of these languages (like Java) wouldn't allow us to create an Object of an Abstract class, but they do allow us create an Array of Object of an Abstract class.
Like,

myclass1 arr[] = new myclass1[10];

We can create an array of 10 objects.

I have some confusion about how this kind of array works.  How do I use this array?
What is the actual use of this array in real-life projects?
Any explanation with an example will be very useful.

In statically-typed object oriented languages (like Java), you can not create an object of an abstract class.  Abstract classes are (usually) not completely defined, so creating such an object wouldn't make any sense.

What you can create is a reference to an object instance of an abstract class.  A reference is just a pointer to an object, not the object itself.

myclass1 arr[] = new myclass1[10];

Creates an array of 10 null references to objects of class myclass1.

Similarly

myclass1 x = null;

Creates a copy of the null reference and casts it to a reference to a myclass1.

You can always assign an object of a (non-abstract) subclass of myclass1 to a reference to myclass1.  So for example:

x = new ConcreteClass();

(where ConcreteClass is a subclass of myclass1).

Any element of arr is also a reference to myclass1.  So:

arr[7] = new ConcreteClass();


Time complexity of BFS with min heap Given a matrix of size m x n, I am trying to traverse it using BFS from top left corner to bottom right corner. Instead of using a normal queue for BFS, I am using a min heap. For each cell, I am inserting the adjacent values (top, left, right, bottom) in a min heap.
I am specifically trying to understand how big the heap would grow. I know that BFS traversing would cost me O(mn) and each heap insertion would cost me O(logk) where k is the size of the heap. Here I am trying to figure out how big can be k.
e.g

[
[1,2,3,4,5],
[2,3,4,1,3],
[4,3,2,1,4]
]

My thoughts are that at max there can be m x n elements in the heap. So the overall complexity can be O(mnlogmn). But when I run through some examples, I think not everything will be in the heap all the time. A single cell can at max insert 2 elements (other 2 would have been inserted by some other cell already). So based on the examples I am thinking that it should be O(mnlog(m+n))

Yes.  Both bounds are valid.  There's not much difference between the two bounds.

There are certainly at most $mn$ items in the queue at any time, as there are only $mn$ possible items.  Consequently, the running time is at most $O(mn \log(mn))$.

By analyzing how BFS visits nodes and the size of the "fringe", one can show that the size of the fringe is most $m+n$.  In particular, the fringe is a path that goes from somewhere on the top of the matrix to somewhere on the left of the matrix, by going only down, left, or diagonally down-and-left (but never right or up).  Thus the fringe can include at most $m+n$ cells.  This means that at every stage, the size of the heap is at most $m+n$, so $O(mn\log(m+n))$ is also a valid upper bound on the running time.

These two bounds are pretty close, so either is a reasonable upper bound on the running time.

Caveat: there are multiple heap data structures, with different running times for the heap operations.  This answer assumes you are using a heap data structure where inserting into a heap containing $k$ items can be done in $O(\log k)$ time.