Given a list of integer rectangle areas, find all integer rectangles that they can tile Is there an efficient algorithm that takes in a list (multiset) of integer rectangle areas and finds all possible integer rectangle tilings?
Every integer rectangle area in the list (multiset) must be used exactly once (corresponds to exactly one rectangle).

For example, if we were given $$(2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1, 1, 14, 1, 1, 16, 1, 1, 18, 1, 1, 20, 1)$$
then one possible integer rectangle tiling is:

which uses the given list to tile a $11\times 12$ rectangle.
So far, I've found What rectangles can a set of rectangles tile? on MO, and am trying to track down and adapt the references to my problem.
A similar but different problem is Filling rectangles with integer-sided squares.

This answer assumes that you only allow the tiles to have integer sides.
There are always some trivial tilings, in which the rectangle being tiled has either a single row or a single column. Counting the number of these is simple combinatorics. Let us show that deciding whether there are any other tilings is NP-complete (under randomized reductions, or assuming some number-theoretic conjectures). It is clearly in NP. To show that it is NP-hard, we reduce from PARTITION. An instance of PARTITION is a multiset of positive integers, and the problem is to determine whether it can be partitioned into two multisets with equal sum.

We start by showing that PARTITION is NP-hard even if all parts are odd and the total sum is divisible by 4. Let us first ignore the latter requirement. Given an instance $S = \{x_1,\ldots,x_n\}$ of PARTITION, construct an instance of the new problem with $S' = \{2nx_1+1,\ldots,2nx_n+1\} \cup \{1^n\}$ (here $1^n$ mean $n$ many $1$s).
If the original instance can be partitioned into two equal parts, say $\{x_1,\ldots,x_m\}$ and $\{x_{m+1},\ldots,x_n\}$, then so can the new instance. Indeed, consider the multiset $\{2nx_1+1,\ldots,2nx_m+1\}$, together with $n-m$ many $1$s. This multiset sums to $2n(x_1 + \cdots + x_m) + m + (n-m) = 2n(x_1 + \cdots + x_m) + n$. Similarly, the remaining numbers sum to $2n(x_{m+1} + \cdots + x_n) + (n-m) + m = 2n(x_{m+1} + \cdots + x_n) = n$, which is identical.
Conversely, suppose that $S'$ can be partitioned into two equal parts, say one of them consisting of $2nx_1+1,\ldots,2nx_m+1$ together with $r$ many $1$s. It follows that
$$ 2n(x_1 + \cdots + x_m) + m + r = 2n(x_{m+1} + \cdots + x_n) + (n-m) + (n-r), $$
and so
$$ 2n(x_1 + \cdots + x_m - x_{m+1} - \cdots - x_n) = (n-2m) + (n-2r). $$
Since $1 \leq m \leq n-1$ and $0 \leq r \leq n$, the right-hand side is in the range $[-(2n-2),(2n-2)]$. Since the left-hand side is a multiple of $2n$, we conclude that the right-hand size is zero, and so $x_1 + \cdots + x_m = x_{m+1} + \cdots + x_n$.
Let us now attend to the sum of $S'$. If $S$ sums to $2R$ then $S'$ sums to
$$
2n \cdot 2R + 2n = 2n(2R+1).
$$
Therefore if $n$ is even, then we are done. Otherwise, we can replace $n$ with $n+1$ throughout (equivalently, add a zero to $S$).

We now reduce the PARTITION variant to the tiling problem.
Let $S$ be an instance of PARTITION in which all numbers are odd and the sum is $2T$, where $T$ is even. Let $p$ be a prime in $(2T,3T)$. Notice that $S \cup \{p-T,p-T\}$ can be partitioned into two equal halves iff $S$ can (this is since $2(p-T)$ is larger than half the total sum, which is $[2T+2(p-T)]/2 = p$). Moreover, since $p$ is odd and $T$ is even, $p-T$ is odd.
Let $q \in (2p,3p)$ be a prime, and consider the instance $S \cup \{p-T,p-T,pq\}$. If $S$ can be partitioned into two equal halves, then we can tile a rectangle of dimensions $p \times (q+2)$ by taking a rectangle of dimensions $p \times q$ and adding two more columns corresponding to the two equal halves of $S \cup \{p-T,p-T\}$.
Conversely, suppose that $S \cup \{p-T,p-T,pq\}$ can tile some rectangle. Since $p,q$ are prime, the rectangle of area $pq$ must have dimensions $1 \times pq$ or $p \times q$ (up to switching the axes). In the former case, since all remaining numbers add up to $2p < pq$, we end up with a trivial tiling. In the latter case, since $2p < q$, the remaining numbers are not enough to fill any rows, and so we conclude that the tiled rectangle must have exactly $p$ rows. Since the remaining numbers add up to $2p$, they must tile a $p \times 2$ rectangle (or two $p \times 1$ rectangles, which is a stronger requirement). The remaining numbers are all odd, and so must correspond to rectangles with a single column. This is only possible if they can be partitioned into two equal parts.


Can we load the data on the bus on multiple registers at the same time? So in the book that I'm reading it says at a time only the data of one register can be on the data bus and only one register can load the data. the first part i get but what about the second part?

why can't we just turn on the load parameter for both of the registers at the same time?

I'm studying for computer architecture and this is the bus that I'm talking about:

Computer

so can we transfer the data from one register to multiple registers with 1 clock?

like transfer the content of AC to PC and DR with one clock?(turn on the load parameters for both of DR and PC at the same time? why can't we do that?)

If we somehow turned on multiple load signals at the same time, in theory it should work to transfer the same value to multiple registers in the same cycle.

(Depending on the hardware design technology, there may be some power considerations, such as amplification of the data bus lines as they go into the various registers, since more gates are consuming the data bus lines concurrently; it is possible that such is required anyway, though.)

However, the diagram you're showing doesn't reveal the answer.  Here's the issue: it doesn't show how the load signal is generated and delivered to the various registers.  So, we can't really tell.

If the load signal is driven by an ordinary MUX (under control of say, instruction decode, e.g. some field of the IR), then by design, it would only ever turn one line on at a time, meaning the answer is no.

But an alternate implementation could turn on multiple registers' load signal simultaneously, so in that case, then yes.

See also Register File, regarding "ports", in how processors with general purpose registers deal with the need to read and write them concurrently.


"not provable", what does this to do with unification? I found one interesting point in nominal unification. Just after proposition 2.16 of Nominal Unification by Urban, Pitts, and Gabbay, it said the following, which I found confusing:

  For non-ground terms, the relation $=_{\alpha}$ and $\approx$ differ! For example, $a.\!X=_{\alpha} b.\!X$ always holds, whereas $\emptyset\vdash a.\!X \approx b.\!X$ is not provable unless $a = b$.

The $=_{\alpha}$ is the standard $\alpha$-equivalence and $\approx$ is defined in the paper.

It seems to me that $\vdash a.\!X \approx b.\!X$ has a unifier which is
${a \# x},[X:=(a \, b)X]$ no matter what $a$ and $b$ are according to the unification algorithm in the same paper.

So, I am trying to understand why the paper said the above lines? what is the relationship between something is "not provable " but has a unifier? or I am misunderstanding something?

Hoping someone could clarify this point for me, thanks in advance!

They mean you can't use the rules in Figure 2 defining $\approx$ (and $\#$) to derive $\emptyset\vdash a.\!X\approx b.\!X$.  If you attempt to do it you'll use $\approx$-abstraction-2 followed by $\approx$-suspension at which point you'll not be able to satisfy the premise as $\nabla$ is empty but the disagreement set is $\{a,b\}$.  There are no other applicable rules, so there is no derivation.

Conceptually, though conceptual understanding is not needed to answer this question, what's happening is with an empty freshness environment we're free to replace $X$ with $a$ (or $b$) but $a.\!a \neq_\alpha b.\!a$. This is what it means in the sentences following that quote by $\alpha$-equivalence not being preserved by substitution.  The freshness constraints in $\nabla$ are what disallow such substitutions. So in an empty freshness environment $a.\!X$ and $b.\!X$ can't be unified as their instances need not be $\alpha$-equivalent.

I recommend getting more familiar with inductively defined judgements and derivations, as e.g. discussed in Chapter 2 of Robert Harper's Practical Foundations for Programming Languages. You should do the exercises there, and write out the complete derivations for the examples in the Nominal Unification paper. Ultimately, checking derivability like this should be as straightforward and mechanical as checking $(x+3)(x-1) = x^2+2x-3$.


does mathematical function set in Genetic Programming can have two input values? I create an individual in GP by using the full method. My individual trees have the same shape and size. I use a binary tree with all the leaves in maxdepth.

The problem is, I can not use the mathematical function set because it accepts two values. therefore I changed mathematical function set like sin (val1) to sin (val1+val2), sin (val1-val2) etc. in order to receive two values. ex

sin() become sin(+), sin(-), sin(/), sin(*)
round() become round(+), round(-), round(/), round(*)
sqrt() become sqrt(+), sqrt(-), sqrt(/), sqrt(*)

Is this allowed? If you can please show me the journal using this method.

There are a couple of weird ideas here, I think. First, generally, you're not going to have all your trees the same size and shape. The algorithms should be allowed to create variations there.

Second, you should certainly be able to use functions with more than one argument. You can do this a number of ways. One, give each operator a "class" that you use to determine where it may legally appear. For instance, the "+" operator might be defined to take two operands, and thus it could only appear at a node with two children. Alternately, you can take the Common Lisp approach and simply define the result of applying those operations on too few arguments. For example, you might take that "+" operator and fill out any missing operands with 0s, so that applying (+) yields 0, (+ 5) yields 5, etc.

You're the one writing the program. You're allowed to make it behave however you like. I don't think you'll find a lot of references in the literature about this sort of thing because, honestly, it's an implementation issue that isn't interesting enough to publish.


Can Double Hashing return the same value 2 times? $h(i,k)=(h^{}_{1}(k)+i * h^{}_{2}(k)) mod |T|$

as it defined in wikipedia

I would like to know if it possible that Double Hashing return the same value for given $k$ when $i=1$ and $i=2$. Or from the other side, is it possible to build $h^{}_{2}$ in such way to that it never happen?

Let's demonstrate what you ask with a complete example. Let's say we have a table of size $|T| = 10$, in which we use double hashing to insert-search for an item. Initially we try to insert-search for an item using $i = 0$. This means we try at location $h_1(k)\mod 10$ let's say that is $3$. If there is collision we try at the next position that is at distance $h_2(k)$ from the current position. Or in other words we try for $i = 1$ thus at position $(h_1(k)+ h_2(k))\mod 10$ and so on. Usually $h_2(k)$ is build in such a way that gives values in the range [1, 10). So given an initial position if we move  less than the 10 positions (but at least 1) there is no way to hit the same location again. You can think table $T$ as a circular buffer. That is if we index a position out of the it's length we wraparound from the beginning of the buffer. So if initial position is 3 the next 9 positions are in sequence $4,5,6,7,8,9,0,1,2$.

So $h_2(k)$ gives the minimum length we move forward to probe for an empty position. This step is always < |T|. So from step to step there is no way to hit the same location.

You may wonder now that if  we miss to find an empty location to insert our k (or in case of search we don't hit k) after several tries (increments of i) then there is possibility to probe some location again after a lot of tries. That is true, but please correct me if I am wrong, that will happen if the load factor is high enough. In such a case you should use a bigger table size of try to fit in it smaller amount of items.

As far as I searched usually the $h_2(k)$ has the form $m - k \mod m$ where $m$ is the biggest prime smaller than |T| so $h_2(k)$ will always be $\neq 0$ and $< |T|$


Is following observation on Ladner's theorem correct? Suppose $NP\subseteq DTIME[n^{f(n)}]$ where $f(n)$ is any function satisfying $\omega(1)$ then is it true $P=NP$ holds?

Ladner's theorem states infinite time hierarchy between $P$ and $NP$. That is there are $NP$ problems in $DTIME[n^{g(n)}]$ for any $g(n)$ such that $n^c\leq n^{g(n)}\leq 2^{n^{1/c}}$ at some fixed $c\geq1$. If $NP\subseteq DTIME[n^{f(n)}]$ where $f(n)$ is any function satisfying $\omega(1)$ then for every such $g(n)$ we can find a $f(n)\ll g(n)$ and so Ladner's theorem is violated and so $P=NP$ has to hold.

And so if $P\neq NP$ there is $g(n)$ with $n^c\leq n^{g(n)}\leq 2^{n^{1/c}}$ such that $NP\subsetneq DTIME[n^{g(n)}]$ and $NP\subseteq DTIME[n^{f(n)}]$ where $f(n)$ is any function satisfying $\omega(1)$ implies $P=NP$. Are these observations correct?

  What if I replace $DTIME$ by $RTIME$? Would this yield $RP=NP$ by some randomized version Ladner's theorem?

I'm annoyed at both ["any" being used as a quantifier] and [the placement of quantifiers making things even more ambiguous], so I'll start with the two interpretations of your initial block-quote.

  Suppose there is a function $\hspace{.04 in}f$ in $\omega(1)$ such that  NP $\subseteq$ DTIME$\left[\hspace{-0.02 in}n^{\hspace{.04 in}f(n)}\hspace{-0.03 in}\right]$ .

  Does it follow that  P = NP ?

It's not known to, since    ($n\mapsto 2^{\hspace{.02 in}n}\hspace{-0.03 in}$)  $\in$  $\omega(1)$    and  NP $\subseteq$ EXP $\subseteq$ DTIME$\left[\hspace{-0.02 in}n^{\hspace{.04 in}(2^{\hspace{.02 in}n})}\hspace{-0.04 in}\right]$  are both known.

  Suppose that for all functions $\hspace{.04 in}f$ in $\omega(1)$,  NP $\subseteq$ DTIME$\left[\hspace{-0.02 in}n^{\hspace{.04 in}f(n)}\hspace{-0.03 in}\right]$ .

  Does it follow that  P = NP ?

Yes, since as described in this answer, there exists

a function $\hspace{.04 in}f$ in $\omega(1)$ such that  DTIME$\left[\hspace{-0.02 in}n^{\hspace{.04 in}f(n)}\hspace{-0.03 in}\right]$ = P .

The truth of your "That is ... fixed $c\geq 1$." sentence has nothing to do with Ladner's Theorem

- The empty language and full language, for example, are such NP problems.

For the sentence after that, the g given by  g(n) = c  is such a g, and functions f cannot simultaneously be in $\omega(1)$ and satisfy  f(n) << c ,  so where's the violation of Ladner's theorem?

By the function g I just mentioned, the part of your

"And so if ..." sentence before that sentence's "and" is true.

For the rest of that sentence, see this answer's two block-quotes and its responses to those.

This answer's response to its "there is" block-quote would still apply.

I believe this answer's response to its "for all" block-quote

would also still apply, by a similar argument.


Distribution Optimization Algorithm I'm trying to classify and come up with a reasonable solution for the following problem (abstracted from a real world problem).

Problem

Imagine StackOverflow started offering a subscription where companies could buy X number of impressions per month for a set of tags.

For example, you might be interested in running an ad with 50000 impressions on the following tags: javascipt, typescript, react, nextjs, nodejs, webpack.

StackOverflow "promises" you will get 50000 impressions, but they are free to distribute them across the above tags however they desire (could even be 100% to one tag).

How should StackOverflow optimize the distribution so that they can sell/deliver the maximum number of impressions?

For simplicity, assume:

we know the number of impressions each tag receives per month ahead of time and it doesn't change
each impressions only belongs to a single tag

My Research

I believe this might be similar to the Knapsack or Bin packing problems.

The simplest way to approach this is with a "first-fit" (or maybe better described as "first come, first-serve") algorithm:

Get all active "subscriptions" (impressions & tags), ordered by Created Date ASC
For each "subscription", grab the first tag and "consume" as many impressions as we can.  If the subscription still has remaining impressions, move to the next tag.
Repeat with next subscription

That might play out something like this:

==Inventory==

Tag          Impressions
javascipt    2000
typescript   5000
react        5000
nextjs       5000

== Subscriptions ==

Acme:  8000  (javacript, typescript, react, nextjs)
Stark: 5000  (javacript, typescript)

== Allocation Results ==

Acme:
 - javacript:  2000
 - typescript: 5000
 - react:      1000

Stark:
 - javacript:  0
 - typescript: 0

The optimization for this solution is clearly horrible.  In the example above, while we had more than enough impressions to go around, we allocated the only ones that "Stark" could purchase before we got around to them.

Is there an official name to this problem and what does the optimal solution look like?

If you had only one tag, this would become a knapsack problem: in particular, determining whether you could sell all the impressions would be exactly the subset problem.  Therefore, the problem is NP-hard.

A plausible approach to solve it in practice would be to use integer linear programming.


What happens when the words transfered on the bus are smaller than its width? So what happens if we're transfering  lots of 8 bit words in a 32 bit bus? Does each bus cycle only transfers 8 bit at the time, wasting the other 24 lines of the bus? Or does it transfer 4 words in each bus cycle?

I would say "it depends":

most likely you ask for 8 bits to be retrieved and you get 8 bits and ignore the other 24 lines;
if you know you're dealing with sequential data, that you want to consider bytewise, you could retrieve 4 bytes at a time, but you'll have to split or handle the retrieved 4 bytes in code.

On specific architectures you have alignment considerations.

Specifically addressing your question, no, it is very unlikely a system would retrieve 4 words in each cycle only to then "split" them into single words to process, without a program catering for that itself.


A variant of the set cover problem: Is that a known problem? Can this problem be solved in poly time?

  Input: $S_i \subset \{1,\cdots,n\}$ for $i=1,\cdots, n$.

  Question: Is it possible to select an $a_i \in S_i$ for each $i=1,\cdots,n$, such that $\{a_1,\cdots,a_n\}=\{1,\cdots,n\}$?

Informally, the problem asks for selecting one element from each subset $S_i$ such that the selected elements cover the set $\{1, \cdots, n\}$.

Hint: Form a bipartite graph which has the sets $S_1,\ldots,S_n$ on one side and the numbers $1,\ldots,n$ on the other. Connect $S_i$ to $a$ if $S_i$ contains $a$. You are looking for a perfect matching in this graph.


If we sort a table column-wise and then row-wise why the table is still sorted column-wise? Say we have a $n \times n$ table which elements are sorted column-wise, for example:

$$
\left( \begin{array}{ccc}
2 & 4 & 1 \\
3 & 5 & 6 \\
7 & 9 & 8 \end{array} \right)
$$

I would like to prove that if we sort this table row-wise, it will be still sorted column-wise.

This is one of the steps to prove the shell sort correctness.

Consider some column $i$ and some rows $j < k$. Let $x$ be the element at row $j$ column $i$ after the final sorting, and let $y$ be the element at row $k$ column $i$. We want to prove that $x \leq y$.

Since $x$ ended up in column $i$, there must have been $n-i$ elements in row $j$ larger than $x$. Together with $x$ itself, these are $n-i+1$ elements in row $j$ that were at least as large as $x$. The corresponding elements in row $k$ were also at least as large as $x$, since the columns were sorted. Summarizing, row $k$ contains at least $n-i+1$ elements which are at least as large as $x$. That means that after sorting, the element at position $i$ on row $k$ (that is, $y$) is at least as large as $x$


Trapdoor functions that depends only on NP-hard? As far as I can tell, there are no examples of trapdoor functions which hardness assumptions is merely hardness of some NP-hard problem in worst case. That is, a trapdoor function in which, it is proved that, if there is an PPT algorithm that can invert it with non-negligible probability, then there is a PT algorithm which can solve the worst case of some NP-hard problem.
If I am wrong on the above, can you show me an example of such function?
If I am not, why is it so hard to make such a trapdoor function? Is there a concrete reason why it's hard to develop such function (beside "we haven't figure it out yet")?
This supposedly "duplicate" question (Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems?) doesn't actually answer this question. That question isn't why worst case NP-hard isn't enough to make an encryption out of it. This question is essentially about why there had been no successful attempt at reducing average-case hardness down to worst-case NP-hard, for the purpose of making trapdoor function. There had been problems where average-case is just as hard as worst-case, so the fact that not all problems has worst-case=average-case doesn't mean you can't use different problems where that is true.

The crux of the problem lies in worst to average case reductions. The standard construction of a function which is average case hard is taking a function which is worst case hard and applying all kinds of fancy error correcting codes on its truth table. See Ta-Shma's notes sketching the STV construction. As far as I know, we don't know how to do that for NP (STV starts with a PSPACE hard function).
Even worse, we believe this can't be done for NP. See Bogdanov Trevisan, where it is shown that if an NP complete problem has a worst to average case reduction then the hierarchy collapses. Your problem is not exactly worst to average case reduction, but reducing an NP hard problem to inverting a one way function. However, these are related and Trevisan's paper also rules out such non-adaptive reductions.
More directly related to your question is AGGM, which also rules out adaptive reductions for the case where the size of the inverse image is easy to compute. You might also want to check out this paper. These results are 10-15 years old (STV is around 20), I have no idea if anything stronger was proven since.


Why having a simple multiplication loop and very good avalanche isn't enough to produce well-distributed hash values? Modern non-cryptographic 32- and 64-bit valued hash functions, for example, lookup3, MurmurHash3 and CityHash, have quite sophisticated loops, each iteration of which include many multiplications, XORs and rotates. Why this is needed, since there are good avalanche procedures (32 -> 32 and 64 -> 64 bits), which mix the bits effectively randomly. So, even if this simple loop:

hash = seed;
while (input_len >= 8)
    hash = hash * prime + fetch_8_input_bytes();
... do something for rest 0..7 bytes of input

produce whatever flawed, biased results for similar input (or a certain subset of input), finalizing avalanche:

return good_avalanche(hash)

"fixes" this.

The last deal is direct collisions, but they are often not so important, assuming hash function produce decently little collisions. I think the above multimplication loop does.

What I'm missing?

Insufficient mixing between incorporating blocks of the key radically increases the possibility of collisions - as an example, imagine a hash like the following -

uint32_t badHash(std::vector<uint8_t> key) {
  uint32_t hash = 0;
  for (size_t i = 0; i < key.size(); i++) {
    hash += key[i];
  }
  hash = SomeFunctionWithPerfectAvalanche(hash);
  return hash;
}

Despite the final avalanche, this function is no better than a checksum at producing a good distribution - it is trivially easy for adjacent blocks to cancel each other out. The situation isn't much improved by multiplying the key block by a prime, or performing any other mix to the key block - I can instantly generate collisions by taking two keys that collide under a simple checksum and then applying the inverse of the per-key-block mix to each block of the colliding pair.

A strong hash function has to perform enough mixing between adjacent blocks to ensure that small changes in the key are overwhelmingly unlikely to cancel each other out. Balancing the amount of work done in mixing each key block and in mixing the hash between key blocks is the tricky part of making a fast and robust hash function.

-Austin, author of MurmurHash


Reference asking : High Performance Computer Architecture Topics

Pipelining: Basic concepts, instruction and arithmetic pipeline, data hazards, control
hazards, and structural hazards, techniques for handling hazards. Exception handling.
Pipeline optimization techniques. Compiler techniques for improving performance.
Hierarchical memory technology: Inclusion, Locality properties; Cache memory
organizations,Techniques for reducing cache misses; Virtual memory organization, Mapping and
management techniques, Memory replacement policies.
Instruction-level parallelism: Basic Concepts, Techniques for increasing ILP, Dynamic
scheduling (Tomasulo's Algorithm), Reorder buffer and instruction commit, Branch
prediction and advanced instruction delivery, Speculative execution. Superscalar, Superpipelined and VLIW processor architectures.Array and vector processors.
Multiprocessor architecture: Taxonomy of parallel architectures. Centralized shared-memory
Architecture. Synchronization, Memory consistency, Interconnection networks.
Distributed shared memory architecture. Model of memory consistency, Cache coherency,
Multiprocessing snooping protocol, Multiprocessing directory protocol. Cluster computers.
These are the topics I have to learn.
It will be great help if I am suggested any video resources or books regarding this.
Although I am going through Computer Architecture: A Quantitative
Approach by John L. Hennessy and David A. Patterson . But I need more resources.

This is a pretty good book: Mike Johnson, Superscalar Microprocessor Design, Prentice-Hall, 1991, ISBN 0-13-875634-1.
Having said that, some of the original references are quite readable. For example:

Robert Tomasulo, An Efficient Algorithm for Exploiting Multiple Arithmetic Units
Lynn Conway et al, Dynamic Instruction Scheduling


Hardness of approximation: what decision problem is hard exactly? Just a question for personal comprehension.  Consider the following statement:

  It is NP-hard to approximate Set-Cover within a $(1 - \epsilon) \log n$ factor for any $0 < \epsilon < 1$.

Now, NP-hardness refers to decision problems.So what is NP-Hard exactly here ?

My guess is that the statement is equivalent to saying that the following problem is NP-hard (but I really ain't sure):

  Given a set cover instance $S$ and an integer $k$ with the guarantee that either $S$ admits a cover of size at most $k$, or $S$ has a cover of size at least $k \cdot (1 - \epsilon) \log n$, decide if $S$ has a cover of size at most $k$.

Note that I took set cover as an example, but my question is on problems that are said 'hard to approximate' in general.

Most likely what is meant is the following statement:

If $P \ne NP$, then there is no polynomial-time approximation algorithm for Set-Cover that achieves a $(1-\epsilon) \log n$ approximation factor.

Or, equivalently: the existence of a polynomial-time approximation algorithm for Set-Cover that achieves a $(1-\epsilon) \log n$ approximation factor implies that $P=NP$.

Your proposed formulation at the end of your question might look tempting, but if you want to understand how to formalize the claim, I probably wouldn't suggest formalizing it that way -- that formulation introduces unfamiliar technical issues of its own.  The problem you listed is a promise problem (it's not a decision problem).  Promise problems are weird and some of your intuition that you've built up won't work quite right for promise problems.   Promise problems are weird and counter-intuitive; if you want to build your intuition, often it's best to simply avoid them, rather than try to absorb the messy details involved in formalizing them.


How can I prove the minimum pumping length of finite language? Let L be the set of all strings over {0, 1} whose lengths are at most three. Since L is regular, the pumping lemma holds for L, and thus there is a pumping length p associated with L. What is the smallest possible pumping length associated with L?

For this problem, I think minimum pumping length for this language should be 4, because if pumping length is smaller than or equal to 3, then  $xy^{i}z$  may not be in the given language, because its length could be longer than 3. So, I want to prove that 4 is the minimum pumping length for the given language, but I have no idea how to prove it accurately. The explanation I wrote here is too informal, I think. Can anyone help me?

You explanation sounds good (you want to change "smaller than" in "smaller than or equal to").

Suppose towards a contradiction that the pumping length was $k \le 3$ then, since
$w=000$ is a word of length at least $k$ in $L$, you could invoke the pumping lemma to conclude that $w$ can be written as $w=xyz$, with $|y|>0$, in such a way that $xy^ik \in L$ for any choice of $i \ge 0$.

This is a contradiction since the choice $i=4$ yields a word $w'$ of length $|w'| = |x| + 4 |y| + |z| \ge 4$ for which you simultaneously have $w' \in L$ (by the Pumping Lemma) and $w' \not\in L$ (by the definition of $L$).

In addition, to show that $k'=4$ is the smallest possible pumping length, you need to argue that $4$ is a valid choice for the pumping length.
In your case this is trivial as the pumping lemma gives you a property over the set of all words in $L$ of length at least $k'$. For $k'=4$ this set is empty, which makes the statement trivially true.


How to draw the heap for an array in Java? I have an assignment to draw the heap after an ArrayList and a LinkedList is created.
public static void main(String[] args) {
     List list = new ArrayList();
     list.add(0);
     list.add(1);
     list.add(1);
     list.add(2);
}

and
public static void main(String[] args) {
     List list = new LinkedList();
    list.add(0);
     list.add(1);
     list.add(1);
     list.add(2);
}

So far I have a tree set up for [0, 1, 1, 2] so that it just goes down like a tree from 0, 1 and 1, then 2. But I don't know if that's correct and if it'd be different for the ArrayList and LinkedList.

Heap is an almost complete binary tree. So if you're planning to construct the tree you can just start by filling the values in the tree from top to down and left to right ie, proceed by filling nodes levelwise.
Arraylist or linked list doesn't matter here because both stored the level order traversal of the tree.
Ex. list.add(0), list.add(1), list.add(1), list.add(2), list.add(3), list.add(5)
                              0
                            /    \
                           1      1
                           / \     /
                         2   3  5


Context-free language from grammar I'm on second year IT studies. I can't do this on my own and my teacher is not eager to help. I went that way but I'm pretty sure it's wrong. Please, help :/

Start out by replacing in the grammar all $Z$ by $y$, since from $Z$ this is the only derivation.
Then, you can easily see what $X$ does: from it we can derive $(xy)y^*$ or $(yxy)y^*$, combined can be written as $(xy+yxy)y^*$ as a regular expression (notice that not always you can write down the derivations as regular expressions!)
Now, $Y$ derives either $xy$ or $yX$, and since $X$ derives $(xy+yxy)y^*$, then $Y$ derives $xy+y(xy+yxy)y^*$.
You can now complete the analysis by noticing that $S$ derives either $Yy$ which is $(xy+y(xy+yxy)y^*)y$, or an additional $SX$. I believe from here you already understand what the language is :)


Can a DFA have an empty string as input? Given string w such that every odd position in w is a 1

My solution is

The book's solution is

from my understanding $\epsilon$ should not be an accepted state, however in the book's solution it is. How is it handling this case?

Yes, an empty string is a valid input to a DFA. If this were not the case, DFAs would not be closed under all of the Kleene algebra operations.

In this case, the argument is correct. Think of the problem statement as an implication. If $i$ is an odd position, then $S_i$ is 1.


Handling untrusted string input in printf in C I stumbled upon the MSDN Best Practices for Code Review.
Under the section “Untrusted Inputs”, I found following which I didn't understand properly. Why is the following considered safe?
printf("%s", buffer);

What kinds of guarantees does the C language give regarding the behavior of this snippet? Given that both printf(buffer) and printf("%s", buffer) are accepted by the compiler, why is one considered safer than the other — shouldn't the unsafe version be rejected?

Copied following text from the source:

Untrusted Inputs
If the input buffer comes from an untrusted source, this can result in a security attack, as the input can contain formatting specifiers that will pull data off the stack. Additionally, it can cause buffer overflows by expanding the resulting string beyond expected limits:
printf(buffer);
These should always be converted to the following:
printf("%s", buffer);

Since you asked on a computer science site, I'll give you a computer science answer. This might not be the most directly helpful from a programmer's point of view, though understanding this will definitely make you a better programmer.

The first argument to the printf function is a char *, i.e. a pointer to a byte¹. However, not all pointers to bytes are valid arguments to printf. The type system of C is not precise enough to express the type of the argument.

It's well-known that the first argument to printf must be a string. A string, in C, is a zone of memory (i.e. a region of bytes with contiguous addresses) which is not empty and where the last byte has the value 0. The string is designated through a pointer to its first byte. A string is isomorphic to an array of nonzero bytes.

A null pointer, or a pointer value that does not point to a valid object, are not valid first arguments to printf. C does not offer any guarantees when a program is invalid. If you pass an invalid argument to printf (or any other function), **the behavior is undefined--. That means the behavior of the program is at the whim of the implementation. It may cause your program to crash. Or to print nonsense. Or to make demons fly out of your nose². Or to execute some code which was specially chosen by the attacker who specified the first argument — in a security context, undefined behavior is typically whatever the attacker has decided it to be (that's what exploit writing is all about).

Not all strings are valid first arguments to printf. The most obvious restriction is that the string must be a format string. In a format string, the character³ % has a special meaning. For example, "%B" and "%0s" are not valid format strings in standard C. A string which isn't a well-formed format string isn't a valid first argument to printf.

It gets worse. Not all valid format strings are valid first arguments to printf. For example, the call printf("%s") is not well-formed: the format specifier %s consumes an argument, but there is none; the behavior of this call is undefined. In practice, in many implementations, printf will grab the value at the top of the stack and assume that it's a valid string; this may crash, print out confidential information, print out data that whatever is reading the output of the program won't understand, or any combination thereof.

The type of printf is really a dependent type: the number and type of subsequent arguments depends on the value of the first argument. This is very far beyond the capabilities of C's type system⁴. Like just about everywhere in C, the onus is on the programmer to write a correct program.

Conceptually, a call like printf(buffer) is wrong, because a buffer is an arbitrary string, whereas the argument to printf must be a printf format. All printf formats are strings (the type of formats is a subtype of the type of strings), but not all strings are printf formats. The call printf(buffer) is only valid if the string buffer happens to be a printf format with zero arguments. This means no format specified other than %%, in standard C; in other words, the valid values of buffer in printf(buffer) are the strings where every % is followed by another %.

If you have a string lying around, how do you know whether it's a valid printf format? If the string is a literal written syntactically within the printf argument list, then it is very easy for the programmer or a code reviewer to check whether the format is correct. Any good compiler can check the format string and report a compilation error if it is incorrect, too. If the string comes from a variable, verifying that it is correct is a lot more difficult.

The correctness of the printf call becomes more and more difficult to ascertain as the value of the format string is specified further and further from the point of use. This is where trust comes into play. In order for the program to behave as desired, the format string must be valid for the call. When you claim that your program behaves as desired, you rely on the format string being valid — in other words, you trust the format string. This is only valid if you trust the entity where the format string originates to provide a valid format string. If the format string comes from a source that is external to your program, that source is often untrusted. Even when it is trusted, tracing that source is a heavy burden, which makes relying on such an external source bad engineering practice.

As a parting piece, why is printf("%s", buffer) valid? The %s format specifier expects a string, so this call is valid if and only if buffer is a valid string. This is as safe as it gets in C.

¹  It's in fact a little more complicated, because char isn't exactly a byte, but for our purposes here it's close enough.
²  Sadly, many computers lack the hardware device that would make this very educational behavior possible.
³  By “character”, I mean the byte whose interpretation in the execution character set is the % (percent) character.
⁴  There are languages where printf is provided and has a type that describes its behavior. The obvious way to do it is in dynamically typed languages like Lisp, Perl, etc., where the behavior of printf if the arguments are not well-formed is to signal an error. OCaml typechecks printf statically; it requires that the format string be known at the compile time, as the compiler parses it and deduces the type of the remaining arguments.


Doesn't a quantum algorithm being deterministic contradict the superposition principle? How can the EQP quantum complexity class exist? I mean, doesn't the superposition principle imply it is not possible to know with probability 1 whether a quantum algorithm will return a solution?

For if a quantum computer’s state is in superposition, quantum measurement implies the state we obtain when we read the computer's state is random - with the probabilty we will obtain any particular state being based on its probability amplitude at the time of measurement. Thus unless some state has probability amplitude 1 (which would mean the system wasn't in superposition, so can't have been a quantum algorithm, as any quantum algorithm must use superposition), we cannot know whether we will obtain a solution state at any quantum computation's completion.

If the algorithm has no error, then the system is not in a superposition when it is measured, but it is possible it was in a superposition during the computation, after which it was cleverly interfered constructively on the right answer(s) and interfered destructively on the wrong one(s).

For example, Deutsch's algorithm has this property, the way he initially introduced it: the system is put into a superposition without entanglement, then it is operated on to produce a superposition in which the two qubits are entangled, and then it is operated on some more so that the final measurement is deterministic.

One way to understand why some deterministic quantum algorithms use superposition is to see that an algorithm is a map from input vectors to output vectors. A good algorithm goes from the input vector to the output vector via the shortest path. The only steps that it can take are elementary gates (Hadamard, CNOT, X, Y, Z, etc.). Sometimes, the shortest path happens to be one in which the intermediate states are in a superposition, even if the final state is not. If this is the case, if all shortest paths involve superposition, then this problem is solvable more quickly by a quantum computer than by a classical computer, which cannot take those paths.


Possible complement of $L =\{a^n b^{n+1} : n\geq0 \}$ The language was $L =\{a^n b^{n+1} : n\geq0 \}$.

This is my attempt:
I believed $L$ can also be expressed as:
$L =\{a^n b^{n}b : n\geq0 \}$
This implies that the number of $b$'s is always greater than the number of $a$'s. Thus, the complement is
$L' =\{w: w\in\{a,b\}^*: n_a(w)>n_b(w)\}$ or $L' =\{w: w\in\{a,b\}^*: n_a(w)\geq n_b(w)\}$.

Once we've fixed the alphabet, the complement is simply the set of all strings over that alphabet that don't have the form $a^nb^{n+1}$. Presumably, here, the alphabet is $\{a,b\}$.  Again, once the alphabet is fixed, there is only one complement.  You've given two and it's unclear whether you mean "I'm not sure which of these answers is right" or "It's the set of all strings that are either like this or like that."

In fact, neither of your two answers is correct. The complement also includes the string $abbb$, even though it has more $b$s than $a$s.


Can an alphabet for a Turing machine contain subsets of other alphabets? For example;

Is {0,1,{a,b,c},d,e} a valid alphabet to form a language over and is it usable in any context?

An alphabet is a set of symbols, therefore if your you treat $\{a,b,c\}$ as a single symbol (in some other alphabet), it is a valid alphabet.


Confusion related to time complexity of fast fourier transform I have this confusion related to the time complexity of FFT. I was reading this book related to Design and Analysis of Algorithms and I came across FFT.

It says that lets say I have a polynomial of degree n-1. I want to evaluate the polynomial at $2n^{th}$ roots of unity. For that I can use divide and conquer rule

I will divide my polynomial into evens and odds i.e,

$A(x) = A_{even}(x^2) + xA_{odd}(x^2)$

Now if I want to evaluate A at one of the  $2n^{th}$ roots of unity. I can break it into evaluating the $n^{th}$ root of unity at two polynomials $A_{even}$ and $A_{odd}$ and then add the results with complexity O(n).

They have shown the results to be O(nlogn). However, I think this is for evaluating the value of the polynomial at one of the roots not all the $2n^{th}$.  But the book seems to say it is the total complexity. I am a bit confused.

Can anyone please explain this to me? I am confused

If you compute by recursion each unit root at a time, it will indeed be costly. However, observe that when you compute $A_{even}(\omega_{n/2}^i)$ and $A_{odd}(\omega_{n/2}^i)$, you actually gain two values for $A$. For $i< n/2$ we have that:

$A(\omega^i_n)=A_{even}(\omega_{n/2}^i)+ \omega_{n}^i\cdot A_{odd}(\omega_{n/2}^i)$

$A(\omega^{i+n/2}_n)=A_{even}(\omega_{n/2}^i)+ \omega_{n}^{i+n/2}\cdot A_{odd}(\omega_{n/2}^i)$

This ability to compute two values using a single computation of $A_{even}$ and $A_{odd}$ allows for the divide and conquer approach to reduce the time to $O(n\log n)$.


Does every turing machine have an equivalent, single-state, n-tape turing machine? Is it the case that every problem computable by a Turing Machine can also be represented by some kind of equivalent n-tape Turing Machine which one has only one state?  (We can assume that the accept and reject states are implicit here. If that bothers you, you may think about this as a question about 3-state machines instead.)

Yes, there always exists a machine, and we really only need 2 tapes.

Your standard TM transition might be written:

$\delta(S_n, a) = (S_m, b, r)$

This would mean that, from $S_n$, if we read $a$, we would write $b$, move in direction $r$, and transition to state $S_m$.  We will allow our machine to move left, right, or stay in place ($<$, $>$, or $-$).

Now for the 2-tape machine, we'll go to our infinite shelf of Turing Machines and grab a standard two-tape model where both heads have independent left/right/stay capabilities.

As it turns out (just our luck!), on this machine, one of the motors actually broke a few years ago, so the second head can still read and write, but it can't move left or right any more.  Not to fear, we won't be needing that motor.  This machine will serve our needs just fine.

This model happens to be called the TwoTapey. On the TwoTapey, we could write a transition this way:

$\delta(S_n, a_1, a_2) = (S_m, b_1, b_2, d_1)$

This transition would mean that, from $S_n$, if the TwoTapey reads $a_1$ on tape 1 and $a_2$ on tape 2, it would transition to $S_m$, write $b_1$ on tape 1, $b_2$ on tape 2, and move head 1 $d_1$.  On a normal two-tape TM, we'd need a $d_2$ for the second head, but there's no need for that here, because that darned motor is still busted.

So, to translate our standard TM to the TwoTapey, we need to add each of our original state names as strings into the tape alphabet of the 2-tape machine.  Then, take each transition, and translate it this way:

$\delta(S_n, a) = (S_m, b, r)$

becomes

$\delta(S_0, a, ``S_n") = (S_0, b, ``S_m", r)$

The key is that busted motor.  Since we never move left or right on the second tape, this allows us to imitate our original states by simply using the second tape to hold our old state information.  This allows us to transition from $S_0$ back to $S_0$, but still utilize just as many transitions as we used to have in the original machine.

As CandiedOrange pointed out to me, this is actually a really good way to show that the hardware/software divide is artificial.  All state is just data, and all data is just state.


Line smoothing algorithm that perserve data uniformity Intro:

I'm working with huge data set that i need to plot in browser, and since there may be up to 1M points my idea was to create different representations for different zoom levels

lets say i have 100k points, i would average two-by-two until i get 50k, then i would repeat that until i get below 500 points (my arbitrary threshold)

so on the most zoomed-out level i would draw all 500 points, or part of it, depending of the chart size, and as i zoom in, i would switch to next zoom level (and stream data if user drags selection l/r), and ultimately if user wants to see fine grain details he can zoom to 0 zoom level and see all the fine details.

I actually created this prototype, and its working quite well, except for one thing: side-effect of this is, as you can imagine, that peaks are lost in those iterations of averaging.

I did some research and find about Douglas-Peucker algorithm, and how it can perserve peaks, i did some tests, and it works quite well, but the problem with that is that if it encounters a series of data (y values) [1,1,1,1,5,6,1,1,1,1,1,1] it will smooth that to something like [1,6,1,1] which doesn't work for me since i need to keep ratio of zoom levels like this

n (length of original data) > n/2 > n/4 > n/8 > .....

I read quite few papers on line smoothing, but all algorithms that i found are accepting distance threshold, that they use for smoothing as a parameter, and none of those can accept number of desired output elements, and also, since their goal is to smooth the line, they will transform sequence like this (y values) [1,1,1,1,1,1,1,1,1,1,1] into [1,1]

So, finally, my question:

Is there an algoritm that:

instead of usual distance threshold accepts the desired number of output elements
tries to perserve peaks (as Douglas-Peucker does)
will smooth data uniformly, so even if it gets (y values) [1,1,1,1,1,1] and i say i want 3 outputs, event if it IS in theory correct to smooth as [1,1] i would need to get [1,1,1] instead

Also, please don't be confused by lack of X axis information because it is irrelevant since all data are measured from 1 to n in steps of 1, so there are no N/A values, or blank spots, or values like [1.3,1.4,3]

x is always [1,2,3....n]

Here are two suggestions for you to try.

Suggestion 1: Use a linear filter. Instead of computing the average $x_{2n},x_{2n+1} \mapsto (x_{2n}+x_{2n+1})/2$, try averaging over a larger sequence, e.g. $y_n = (x_{2n-1}+2x_{2n}+2x_{2n+1}+x_{2n+2})/6$.

Suggestion 2: Use a conditional filter: if $x_{2n} < x_{2n+1} > x_{2n+2}$ or $x_{2n-1} < x_{2n} > x_{2n+1}$, then let $y = x_{2n+1}$ or $y = x_{2n}$, respectively, and similarly for local minima; otherwise use the average (or a linear filter) as before.


Sum of distances between points on one-dimensional axis We have given integer array of $n$ points, let it be $A$, showing where it is on the x-axis. For this problem we are working only with the x-axis and the y-axis is not important at all. Now for given two indexes $l$ and $r$, such that $0\leq l\leq r \leq n-1$, we want to find the sum of distances from each point whose index is in the range $l, r$ to the point with index $r$.

For example $A = \{1, 2, 4, 6, 8\}$ and $l = 0$, $r = n-1$ The output should be $(8-8) + (8-6) + (8-4) + (8-2) + (8-1) = 0 + 2 + 4 + 6 + 7 =19$

I know that it can be implemented in $O(1)$ after $O(N)$ preprocessing but I don't get the intuition behind that, and the formula is very unclear to me.

Let us start with the formula for the sum of distances:
$$
\begin{align*}
D(\ell,r) := \sum_{i=\ell}^r [A_r - A_i] &= (r-\ell+1) A_r - \sum_{i=\ell}^r A_i \\ &= (r-\ell+1) A_r - \sum_{i=1}^r A_i + \sum_{i=1}^{\ell-1} A_i.
\end{align*}
$$
In time $O(n)$ we can compute an array $B_i = \sum_{j=1}^i A_j$: indeed, $B_0 = 0$, and $B_j = B_{j-1} + A_j$. The formula above then translates to
$$
D(\ell,r) = (r-\ell+1)A_r - B_r + B_{\ell-1},
$$
which can be computed in $O(1)$.


Why is two-phase commit better than naive master-slave replication? In the context of a distributed database, I'm trying to understand why 2PC (as described in e.g. https://www.cs.princeton.edu/courses/archive/fall16/cos418/docs/L6-2pc.pdf) is better than the following hypothetical protocol between a client, master, and slave:

client tells master to commit
master commits it
master tells client the commit succeeded
master tells slave to replicate the commit. If the slave fails, master keeps on trying until it succeeds and gets the slave caught up on all edits.

This seems to me to satisfy the same properties as 2PC:

Safety: If the master commits, the slave will also eventually commit. If the slave commits, the master must have committed first. I suppose an advantage of 2PC is that if a participant fails before starting the commit, the transaction will be failed instead of only committing on the TC. However, in the proposed protocol, the commit on the master still eventually gets to the slave.
Liveness: This protocol does not hang.
Both rely on the master / TC durably recording the decision to commit. Both assume failed slaves / participants eventually wake up and catch up with the master / TC.
Both fail if the master / TC goes down.
In both protocols, it's possible to have temporary inconsistencies where the master / TC has finalized a decision, but the slaves / participants haven't yet committed.

It seems to me that the key theoretical difference in 2PC is that the participant (slave) can vote "no" to the commit, as opposed to merely temporarily failing. That would break the conclusion above where the slave eventually catches up. However, I don't see why the slave would need to vote "no" in the first place. Given the assumption that the slave / participant does not permanently fail, it seems it should either vote "yes" or fail to respond. (Unlike the bank account example, I expect the slave to blindly replicate the master.)

Distilling all this down, it seems to me that 2PC's assumption that participants don't permanently fail makes it unnecessary to give participants a chance to vote "no" in the "prepare" phase.

What am I missing here? Presumably there's some advantage to 2PC over the above that I'm not understanding, since 2PC is actually used to build distributed databases.

Am I incorrect in concluding that a slave shouldn't need to explicitly vote "no", as opposed to temporarily failing? (I'm only talking about the data replication use case, rather than the bank account example.)
Given the same assumptions as 2PC, and assuming slaves only say "success" or "try again", is there some guarantee 2PC offers that the naive replication above doesn't?

For the purpose of the question, I'd like to ignore practicalities, unless they're critical to the answer. In particular, I'd like to ignore things that could be interpreted as being disallowed by the no-permanent-failure assumption, such as  disk full, slave mis-configured, slave corrupt, operator error, buggy software, etc.

You are confusing the purpose of the algorithms. The 2PC is a voting algorithm where the two sides have different data and different criteria for choosing a vote. The master-slave is a redundancy algorithm that aims to have identical copies at two places.

Besides, your master-slave is asynchronous where you return to client before replication. The client sees completion but the master can still become irrecoverable before replication, at which point you have data loss. 2PC is not subject to this.

That said, organizations may use 2PC in to implement master-slave, by making the “slave” always vote yes. This is essentially master-slave in synchronous mode, with unnecessary message overhead.

What you want to advocate for is probably synchronous master-slave, where you return to client after the slave confirms. It’s faster than 2PC because you only need one message exchange for each slave, instead of the two exchanges required for 2PC.


Algorithm undirected graph to directed strongly connected graph For an undirected connected graph $G=(V,E)$ given as adjacency list I want to find a directed strongly connected graph $G=(V,E')$ where each $e' \in E'$ is either $(u,v)$ or $(v,u)$ if we look at its original $e=\{u,v\}$. Also we're assuming  there are no bridges in the given graph G (which I'm checking before hand).

The idea is that if we find a cycle in $G$, then we can orient its edges so that the nodes in the cycle will be all strongly connected. The cycle can then be collapsed into a single node. If the graph had no bridges the new graph will also have no bridges and this procedure can be repeated. Eventually, you will be left with a single node, meaning that the whole graph is a single strongly connected component, as desired.

More precisely, you can iteratively do the following:

Find a cycle $C $in $G$;
Orient the edges of $C = \langle u_1, u_2, \dots, u_k, u_{k+1} = u_1 \rangle$ in an arbitrary but consistent direction w.r.t. $C$. For example, for $i=1, \dots, k$ orient $(u_i, u_{i+1})$ towards $u_{i+1}$;
Orient the chords of $C$ in an arbitrary direction.
Identify the vertices in $C$, possibly creating parallel edges (but ignoring self-loops). This means replacing $u_1, \dots, u_k$ with a new super-vertex $\overline{u}$. For every edge $(x,y)$ where $x \in C$ and $y \not\in C$, add a new edge $(\overline{u}, y)$.
Repeat until a single vertex is left in $G$.

Notice that if there are two or more vertices left in $G$ then there must still be a cycle (otherwise there is a bridge that was also bridge in the original graph). This means that you will eventually be left with a single vertex. When this happens, all edges in the original graph $G$ must have been assigned a direction and you are done.

If you think of using the above algorithm while performing a single DFS visit to discover the cycles to contract, then all the cycles $C$ will be of the form $\langle u_1, \dots, u_k, u_{k+1} = u_1 \rangle$, where for $i=1,\dots,k-1$, $u_{i}$ is the parent of $u_{i+1}$ in the DFS tree, and $(u_k, u_1)$ is a back-edge. If you use the above choice for the orientation of the edges of $C$, then this is equivalent to this simpler algorithm:

Perform a DFS visit of $G$ from an arbitrary vertex $r$ to obtain a tree $T$.
Orient all the edges of $T$ away from $r$.
Orient the edges not in $T$ towards $r$ (notice that this is well defined since there will be no edges between two nodes at the same depth in $T$).

You can also give a direct proof that the orientation $G'$ computed by this second algorithm is a strongly-connected graph. It is clear that there is a path from $r$ to any other vertex in $G'$. The following claim implies the converse.

Claim: Let $(u,v)$ be an edge of $T$, with $u$ being the parent of $v$. There is a path from $v$ to $u$ in $G'$.

Proof:
Since $(u,v)$ is not a bridge, there must be a cycle of the form $C = \langle u_1 = u, u_2 = v, u_3, \dots, u_k, u_{k+1} = u_1 \rangle$.
Let $i$ be the smallest index in $\{1, \dots, k\}$ such that $u_i$ lies in the subtree $T_v$ of $T$ rooted at $v$ and $u_{i+1} \not\in T_v$ (this edge must always exist).
Since $u_i \in T_v$, there is a (possibly empty) directed path $P$ from $v$ to $u_i$ in $G'$.
Since $u_{i+1}$ is an ancestor of $v$ and $u_{i+1} \not\in T_v$, $u_{i+1}$ must be an ancestor of $u$ (possibly $u$ itself). This means that there is a (possibly empty) directed path $Q$ from $u_{i+1}$ to $u$ in $G'$.
Finally, $(u_i, u_{i+1})$ is not a tree edge, hence it is directed towards $u_{i+1}$. This means that $P \circ (u_i, u_{i+1}) \circ Q$ is a path from $v$ to $u$ in $G'$ (where $\circ$ denotes concatenation). $\quad\square$


How can I solve the recurrence $T(n) = 4T(n/2) + n^2\log^2n$? (without master theorem) I can not find the appropriate variable to change the second part $n^2\mathrm{log}^2n$.

You want to use the Master theorem. Writing $T(n)=aT(n/b)+f(n)$, we get that $a=4$, $b=2$, and $f(n)=n^2\log^2n$. This gives $\log_b(a)=2$. This is the same exponent on $f(n)$, but you have an extra $\log^2n$. This fits case 2 on the Wikipedia page. So we get $O(n^2)$ with an extra $\log^3n$. This gives an overall result of $T(n)=O(n^2\log^3n)$.


For how large graphs can we still check for isomorphism? Let $G_1,$ $G_2$  be two arbitrary graphs with $n$ vertices and we want to check if they are isomorphic.

Question 1.  For what maximal value of $n$ we can actually perform such verification?

Question 2.
Is there any result like as  a list of all non-isomorphic graphs up to $n$, and what is the value of $n$ — 10, 20?

The number of non-isomorphic graphs on $n$ nodes is given by https://oeis.org/A000088. If you only care about connected graphs then it's https://oeis.org/A001349. Programs like nauty can enumerate these graphs for you. That answers your second question.

For your first question, it depends on the meaning on actually. There are algorithms which work for fairly large number of vertices, but fail (take a long time) on some bad examples that supposedly don't happen (or are rare) in practice. The worst-case asymptotic complexity of graph isomorphism is still open. The Wikipedia page has an old (2001) reference which compares real-world algorithms for graph isomorphism. Perhaps you could find a more recent one and update the page.


NP-completeness of vertex cover Show that the following language is NP-complete
  $$ L = \{ \langle G,k \rangle \mid \text{$G$ is a graph with a set $S$ of $k$ vertices hitting every edge of $G$}\}. $$

I know I should reduce the problem to SAT. But how I can do it?

A related, but different problem is Independent Set: it asks for a set of $k$ vertices that hits each edge at most once (instead of at least once).

A simple reduction from 3-SAT to Independent Set is as follows:

For each clause, we take a clique on $3$ vertices (i.e., a triangle). Each vertex of this triangle corresponds to specific literal appearing in a clause. E.g., a clause $(x_1\vee \neg x_2 \vee x_3)$ would have vertices corresponding to literals $x_1,\neg x_2,x_3$.
Whenever two vertices correspond to conflicting literals, we make those vertices adjacent. E.g., all vertices corresponding to $x_1$ are made adjacent to all vertices corresponding to $\neg x_1$.

We now ask whether an independent set of size $m$ (the number of clauses) exists.

Note that since there is a partition of the graph into $m$ cliques (created in step 1), the size of a maximum independent set is at most $m$ (one vertex from each clique). If there is an independent set of size $m$, then there is a satisfying assignment: such an independent set much select exactly one vertex from each clique, and which vertex is selected tells us which variable is used to satisfy that clause. This gives a satisfying assignment because the edges added in step 2 ensure that no conflicting literals are selected. Conversely, it is easy to see how a satisfying assignment corresponds to an independent set of size $m$.

This reduction should give you a good idea of how to approach the case for Vertex Cover (but this will require some slight modifications).


Finding an element in a infinite unsorted doubly linked list Is there any way to find an element in an unsorted doubly linked list given an element and pointer from which we can navigate? (we can't use head/tail pointers since the list is infinite)

Infinite/unbounded in both directions?
Zig-zag.


Complexity of numerical derivation for general nonlinear functions In classical optimization literature numerical derivation of functions is often mentioned to be a computationally expensive step. For example Quasi-Newton methods are presented as a method to avoid the computation of first and/or second derivatives when these are "too expensive" to compute.

What are the state of the art approaches to computing derivatives, and what is their time complexity? If this is heavily problem-dependent, I am particularly interested in the computation of first and second order derivatives for Nonlinear Least Squares problems, specifically the part concerning first order derivatives (Jacobians).

The time to compute first-order derivatives (gradients) and second-order derivatives (Hessians) depends heavily on the particular function.

In general, I am aware of three approaches:

Analytical: With pencil and paper, figure out an analytical expression for the derivatives, by using the rules of calculus.  Then implement those expressions.  Here the running time depends entirely on how easy or hard it is to compute those expressions.  In some cases, you may be able to use a computer algebra system to help with this calculation.
Automatic differentiation: Use the computer to do compute the derivatives for you, given a program to compute the function itself.  See, e.g., https://en.wikipedia.org/wiki/Automatic_differentiation.  This will construct a program that evaluates the derivative at a value of your choice.  The running time and ability to do this depends entirely on the program you are differentiating.  Generally speaking, if you are differentiating a function $f$ that can be computed in $O(n)$ time as a straight-line expression (with loop-free code that uses only elementary operations and conditionals, but no arrays or random-access memory lookups or loops), then automatic differentiation can construct a program that evaluates the derivative at an arbitrary input in $O(n)$ time.  This is true even if the function is over multiple variables and you want to compute the gradient.  The Hessian is slower: if $f$ is a function of one variable, you can evaluate the Hessian at an arbitrary point in $O(n)$ time, but if $f$ is a function of $m$ variables, it will take $O(mn)$ time.
Numerical differentiation: You can use the method of finite differences to approximate the gradient, given only a black box that can compute the function (you don't even need the code of that black box).  See https://en.wikipedia.org/wiki/Numerical_differentiation.  Here if you have a function $f:\mathbb{R} \to \mathbb{R}$ of one variable that can be evaluated in $O(n)$ time using some black box, you can approximate the derivative or second derivative in $O(n)$ time.  If $f$ is a function of $m$ variables, you can approximate the gradient at an arbitrary point in $O(mn)$ time, and estimate the Hessian in $O(m^2n)$ time.

Finally, one more method that may be acceptible in some settings is to evaluate the function $f$ at several points, fit a model $\hat{f}$ based on those points, compute or estimate the first- or second-order derivatives of $\hat{f}$ using any of above methods, and use that as an estimate of the corresponding derivative of $f$.

Saying you are interested in "nonlinear least squares" does not narrow things down, because "nonlinear" allows a completely arbitrary function, so long as it is not linear.


Difference between word logical addressing and byte logical addressing in this exercise? I´m new here and this is the first question I´m posting (hopefully this is the correct site).

I have the exercise below:
Consider a virtual address space of 10 pages of 1024 words each (1 word = 2 bytes), mapped onto a physical memory of 32 frames. How many bits are needeed for each virtual address?

The answer they provide is:

| 4 bits for page | 10 bits for offset |

But I don´t figure out how do the 4 bits appear. The exercise explains that the logical addressing is word logical addressing (instead of byte logical addressing).

I´m confused about this two terms. How can I know if the addressing method is word based or byte based?

Thank you in advance

Page size => 1024 words = 2^10 words

Since it is word addressable format 10 bits will be required to identify offset within page.

There are 10 pages as 10 can't be expressed in 2's power format we need to consider 16 for identifying 10 pages i.e. 2^4=16.

So 4 bits are  required for page number.


What areas in EE overlap closely with CS I am doing bachelors in Electronics & Communication Engg.. But most of my work happened to be in Web development.. I am thinking to do my bachelor thesis which very closely overlaps with my recent work.

Are there any specific areas in CS, EE (may be Computer Networking in broad terms) that I can take up?

One very close overlap is of course Computer Architecture.

Another close overlap (which incidentally happens to be my speciality) is EDA (CAD for VLSI designers). EDA requires development of fairly sophisticated parallel algorithms for things such as routing, RC extraction, optical proximity correction, etc., as well as understanding of the underlying VLSI physics.

Other subjects include telecommunication and signal processing, as pointed out in Subhayan's comment.


Are Perceptrons the neural network equivalence of Linear and Logistic Regression? am I right in the assumption that both linear and logistic regression algorithms can be represented as the simplest form of neural networks,a perceptron, which consists of a two layers, an Input and an output, that combines all the input each with it's own respective weight to produces a prediction or classification polynomial?

if this is the case, is anything achievable by Linear or Logistic Regression is also achievable by a perceptron?

Yes, logistic regression can be viewed as a simple neural network with multiple inputs, a single neuron, a single output, and using the logistic function as the activation function.

No, linear regression is not a form of a neural network (a neural network would have a activation function; but there's nothing like that present in linear regression).


Difference between heuristic-based searching and optimal path searching I'm currently studying for an AI computer-science course.
One thing is difficult for me to grasp and somewhat vaguely explained in my course-material:

I understand that with search-methods like e.g. beam search, hill-climbing... you can search based on a certain knowledge about the problem which can tell you in each state an approximation off how close you are to finding the solution. Currently I've reached a chapter about Optimal Search algorithms. An important algorithm in that chapter is Uniform Cost which is based on the lowest accumulated "travel-cost", with as desired consequence that the algorithm will reach a solution in a branch with the lowest accumulated travel cost. Now, I don't understand that travel cost and how it differs from a normal heuristic value. Can someone explain the difference and how it effects finding a solution?

Uniform Cost Search (UCS) does not have a heuristic value and doesn't rely on a heuristic function.  I suspect you're getting it confused with some other algorithm (e.g., A*).  In Uniform Cost Search, there's no heuristic: we know exactly what the distance from the starting point was, and we use that to determine which nodes to expand.


How is `y λx.x y` parsed using the standard pure untyped lambda calculus conventions? How would the following term in the pure untyped lambda calculus be parsed:
y λx.x y
The relevant conventions listed on https://en.wikipedia.org/wiki/Lambda_calculus_definition#Notation (as well as many texts on this subject) state:

Applications are assumed to be left associative: M N P is parenthesised as ((M N) P)
The body of an abstraction extends as far right as possible: λx.M N is parenthesised as (λx.(M N)) and not ((λx.M) N)

There is no priority specified between these two conventions.
In the case of y λx.x y, if the "applications are left associative" rule is first applied, we get (y (λx.x)) y, and if the "abstraction extends as far right as possible" rule is first applied, we get y (λx.x y). Which one is considered correct, and on what basis?
Observations and thoughts:
I have tried this on some online tools, and this is what I observed:

https://projectultimatum.org/cgi-bin/lambda parses y λx.x y as y (λx.x y)
https://crypto.stanford.edu/~blynn/lambda/simply.html cannot parse y λx.x y (result is a parse error)
https://jacksongl.github.io/files/demo/lambda/ also results in a parse error.

I initially thought that the rule "abstraction extends as far right as possible" was equivalent to specifying that application binds tighter than abstraction. But this assumption may be wrong. Under this assumption, y λx.x y would be parsed as (y (λx.x)) y, since the "applications are left associative" rule would kick in first.

The left associativity of applications is only relevant when you have a sequence of applications. If it were correct to interpret y λx.x y as y (λx.x) y, then the left associativity rule would disambiguate it to (y (λx.x)) y. But that interpretation violates the rule that abstractions extend as far right as possible.
Normally one never writes y λx.x y unparenthesized, so I think it's best for parsers to reject it, but if I saw it I would guess that it means y (λx.x y).


Best way for two players to visit a set of graph vertices in a given order I am struggling with the following dynamic programming problem:

  Given a complete $N$ vertex digraph  and a list of vertices $List$, find a way for two players who start at vertices 1 and 2 respectively to visit each vertex from $List$ (order matters, i.e. $List_{i + 1}$ should be the vertex visited after $List_i$). Some vertices may appear in $List$ more than once (multiset). It is sufficient for a vertex to be visited by only one of players (i.e. one of them can visit all vertices while the other would remain at his starting position) If one player makes a move, the other stands still (can't make moves in parallel). If the current vertex to be visited is $List_i$, players must move to it directly, i.e. take either $(List_{i - 1}, List_i)$ edge (since the previous move guarantees one of player is in $List_{i - 1}$) or $(List_j, List_i)$, for some $j < i$ ($List_j$ is the position other player stopped at during some previous move). This means the path with $L$ vertices in it consists of exactly $L$ edges. The weight/cost of the path should be minimal. Weight of edge $(i, i)$ is always $0$, all weights are non-negative integers, no multi-edges or loops are allowed.
  Output the cost of such a path.

This is actually a problem from a Russian online judge. The original problem has three players (starting at $1, 2, 3$) in it and also asks to output what player did visit $List_i$, but I reduced the problem for the case of two players which should just make things easier for perception. I think according to the rules I should provide the link for the source problem even if this is a Russian language only website, so here it is http://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=3379 . If someone really needs it, the stated constraints (that shouldn't matter since we are talking about a simplified version of a problem) for the original problem are $(3 \leq N \leq 200)$ and the number of vertices to be visited is at most $1000$ (I swapped denoting letters), no memory/time limits are given.

The problem has a 2D dynamic programming tag.

My thoughts would be to denote $dp_{i, j}$ as a shortest path that visits vertices from $List_i$ to $List_j$, i.e. $(List_i, List_{i + 1}, ...,List_{j - 1}, List_j)$. The answer is would be stored in $dp_{1, L}$, provided that indexing goes from $1$ and $L$ stands for the length of the $List$. The problem is that I don't have a clear idea how to compute this dp-table. I thought of doing someting like $dp_{i, j} = \min_{k \in i..j}\{ dp_{i,k - 1} + cost(k - 1, List_k) + cost(List_k, k + 1)  + dp_{k+1,j}\}$.
Naturally, I'd at first compute all paths of length 2, then 3 and so on. The thing is, I don't understand how to deal with the main 'problem' of this problem, determining when the move is made by player 1 or 2. I thought there would probably have to be different costs of paths for different players, but they actually use the same graph, so all that matters is the position player $x$ ended up at. Filling the DP-table would actually have to consider two cases, the one described above which is guaranteed to exist as in path $dp_{i,k - 1}$ we know that one of players ended up in vertex $k - 1$.  The case where the other player goes from 'some previous' vertex should be taken into consideration as well,
$\min\{ dp_{i,k - 1} + cost(j, List_k) + cost(List_k, k + 1)  + dp_{k+1,j}\}$
 , where $j$ stands for 'some previous' vertex.  While writing this, I also realized that I'd probably need a little hint how to remember the player that visited vertex $List_i$ which is needed for the original problem.

Could you provide me some help please?

Here is the naive dynamic programming algorithm, which can probably be improved upon: For every $1 \leq i, j \leq |List|$, compute the minimal weight of a path in which Player 1 is at $List_i$, Player 2 is at $List_j$, and the players have covered all vertices up to $List_{\max(i,j)}$. This should run in $O(|List|^3)$.


Randomly choose a line - algorithm We have a large file that can't fit into internal memory. How do we randomly pick one line so that each line has the same probability to be picked?

And how do we randomly pick such n lines so that they all have the same probability?

We don't know the number of lines beforehand.

Any hint on where to start solving this, which algorithm to use, or at least an idea where to start would be appreciated.

Your problem is known as reservoir sampling. The algorithm maintains a currently picked line, whose initial value is the very first line. For $k > 1$, you replace the currently picked line by the $k$th line with probability $1/k$. If there are $n$ lines in total, the probability that the $k$th line is chosen is
$$
\frac{1}{k} \cdot \left(1-\frac{1}{k+1}\right) \left(1-\frac{1}{k+2}\right) \cdots \left(1-\frac{1}{n}\right) = \\
\frac{1}{k} \cdot \frac{k}{k+1} \frac{k+1}{k+2} \cdots \frac{n-1}{n} = \frac{1}{n}.
$$


Selecting k-1 items that divide a sorted array to k equal parts Given an unsorted array of $n$ integers, I need to find an $O(n \log k)$ algorithm that finds the $k-1$ items that divide the sorted array to $k$ equal (up to $\pm 1$ items) parts.

For example, if $k=3$, the items we want would be at indices $n/3$, $2n/3$ in the array after we sort it.

I know that you can select those items in $O(nk)$ but I can't think of how to improve that $k$ to $\log k$. I'd appreciate any help.

I assume that $k = 2^m$ ($m \in \mathbb{N}$) and $k \le n$.

Here is a recursive (divide-and-conquer) algorithm:

Select the median of the array $A$ and use it to partition the array into $A_l$ and $A_r$
Do the same thing above recursively on $A_l$ and $A_r$.

It is easy to see that the depth of the recursive is $O(\lg k)$. Unfolding the recursive tree, you will find that at each depth (i.e., recursion), the non-recursive cost is $O(n)$ for median-selection and partition.

Note that if $k = n$, the algorithm above is the QuickSort algorithm with medians as pivots.


Typing rule for binding groups In "Typing Haskell in Haskell", by Mark P. Jones, is provided a sort of haskell-like specification for typing Haskell. As stated in this paper, binding groups is a area "neglected in most theoretical treatments of type inference". Jones provided inference and checking algorithms for this syntactic construct, but it's typing rule is not referenced.

As far I know, binding groups is quite differente from usual let bindings.
You can have mutual recursion, for example. Also, I don't know if is possible to simulate binding groups only using let expressions.

There is a typing rule for typing binding groups anywhere in the literature?
If there is, then maybe the rest of this question is pointless.

This paper also doesn't give us a (in)formal grammar for the syntax, because it's goal is type inference/checking from the data stucture itself. I don't think this is strictly necessary, but a syntactic definition of binding groups may help defining a typing rule. So, I decided to give a sugestion of what this informal grammar may look like. Brackets means finite sequence and curly bracket means no-empty finite sequence.

So, what I'm asking here is a rule for typing binding groups.

EDIT:

It seems that my question is not clear enough. I apologize for that. I'll try to make it more clear...

By typing rule (or type rule) I mean: en.wikipedia.org/wiki/Type_rule and by type checking algorithm I mean something easy to translate to code. I think the difference is more fundamental than just representation style. A rule is closer to a relation and an algorithm is closer to a function. What is missing is a rule, like in the wikipedia page, that could be used for certification of the algorithm.

Certification is the motivation behind my question. I want to certify the algorithms described in this paper.

I don't know what rule Jones intended to use, but I'd guess it's something like

$$
\dfrac{
\Gamma' = \Gamma,x_1:\tau_1,\ldots,x_n:\tau_n
\\
\Gamma' \vdash e_1 : \tau_1
\\
\cdots
\\
\Gamma' \vdash e_n : \tau_n
\\
\Gamma' \vdash e : \tau
}{
\Gamma \vdash {\sf let}\ x_1=e_1;\cdots;x_n=e_n\ {\sf in}\ e : \tau
}
$$

which handles mutual recursion in groups. The rule above does not consider patterns as in x [p] = e, but it could be amended to support those as well.

I think binding groups are usually neglected since mutual recursion can be translated into non-mutual one (e.g. exploiting Bekić's theorem). However, in a real-world language it's convenient to have mutual recursion, even if from a purely theoretical point it's redundant. Hence, having a typing rule for it and an inference algorithm is still quite useful.


Which law is this expression X+ X’.Y=X+Y Question. Name the law given and verify it using a truth table. X+ X’.Y=X+Y

My Answer.
X   Y   X’  X’.Y    X+X’.Y  X+Y
0   0   1   0       0       0
0   1   1   1       1       1
1   0   0   0       1       1
1   1   0   0       1       1

Prove algebraically that X + X’Y = X + Y.
L.H.S. = X + X’Y
           = X.1 + X’Y        (X . 1 = X property of 0 and 1)
           = X(1 + Y) + X’Y   (1 + Y = 1 property of 0 and 1)
           = X + XY +  X’Y
           = X + Y(X + X’)
           = X + Y.1          (X + X’ =1 complementarity law)
           = X + Y            (Y . 1 = Y property of 0 and 1)
           = R.H.S.      Hence proved.

My teacher marked my answer wrong. And told me to find the correct answer. Friends tell me is it a complementary law or distributive law or Absorption law? If it is absorption kindly tell me how to prove RHS and LHS algebraically.

One way of looking at this is as a consequence of distributivity, where $P+QR\equiv (P+Q)(P+R)$. Then you'll have
$$\begin{align}
X+(X'Y) &\equiv (X+X')(X+Y)&\text{distributivity}\\
&\equiv T(X+Y)&\text{inverse}\\
&\equiv X+Y&\text{domination}
\end{align}$$


Base conversion puzzle Here's an old puzzle: Let $s$ be a string of decimal digits ($s[i] \in \{0,\dotsc, 9\}$). Define a function $f(s)$ as follows:

Interpret $s$ as a decimal number, $n_{10}$, and convert $n$ to its octal equivalent, $m_8$.
Now treat $m$ as a decimal number, $m_{10}$ and convert it to its hexadecimal equivalent, $h_{16}$, and return its hex representation as a string.

For example, if $s= \langle245\rangle$ we would have $245_{10} = 365_8$ and $365_{10} = 163_{16}$ so in this case, $f(\langle245\rangle) = \langle163\rangle$. Similarly, $f(\langle155\rangle)=\langle \mathrm{E}9\rangle$

What are the fixed points of $f$? In other words, for which digit strings $s$ is $f(s)=s$?

I have a few questions about this puzzle:

It's not hard to show that $\{0,\dotsc, 7, 64,\dotsc, 69\}$ are all fixed points. Are these the only ones? I have a proof that they are, but it's inelegant, basically showing that after a certain point, $p(s) < s$, or $p(s)$ isn't a decimal string. Does anyone have a nicer proof, for some value of "nicer"?
I've spent more time than I should in a so-far futile search for a reference to this problem. Does anyone have one? All I know is that it's decades old.

Define $f(s)=h(g(s))$, where $g(\cdot)$ is the conversion to octal and then interpreting the result as a decimal string, and $h(\cdot)$ is the conversion to hexidecimal and then interpreting the result as a decimal string (if possible).  For instance, $g(245)=365$, and $h(365)=163$.

Asymptotically, it is easy to see that $g(x) \sim x^\alpha$, where $\alpha = \log_8 10 = 1.1073\dots$.  In other words, once $x$ is large enough, $g(x)$ is asymptotically proportional to $x^{\alpha}$.  (Why?   Consider $x=8^k$, or $x=a \cdot 8^k$ where $a \in \{1,2,\dots,7\}$.  Once $x$ is large enough, the lower-order terms in the base-8 representation of $x$ become negligible, asymptotically.)  Similarly, asymptotically we have $h(y) \sim y^\beta$, where $\beta = \log_{16} 10 = 0.83048\dots$.

It follows that asymptotically

$$f(s) \sim s^{\alpha \beta}.$$

Notice that $\alpha \beta = 0.9196\dots$, and in particular $\alpha \beta < 1$.  Therefore, asymptotically, $f(s)$ grows more slowly than $s$.

It follows that there is a constant $c$ such that, for all $s>c$, we have $f(s)<s$.  From this it is easy to see that we only need to check finitely many  possible values of $s$: the values $s=1,2,\dots,c$.

All that remains is to determine the constant $c$ explicitly.  This can be done with a bit of algebra; it gets a bit messy, and I don't know of any elegant way to derive it.  But hopefully the above is a relatively clean way to show why your approach has to work, and isolates the messy part to a well-contained calculation.  To me, this is much nicer, because it provides some pretty simple intuition about why there can be only finitely many fixed points.

In other words, this all follows as a consequence of the fact that

$$(\log_8 10) \times (\log_{16} 10) < 1.$$


Are constants faster than variables? It's said that constant references within a program are replaced by the value at compile time, where as, variable references will need to be looked up at run time - making them slower.

Yeah, it sounds faster, but won't they ultimately both be locations in memory (that will have to be looked up), with the difference being that the variable can be altered?

Some machine instruction sets include instructions for which 'small' constants are part of the instruction, either explicitly or implicitly.  E.g the set of 'add' instructions can include 'add immediate', where the value to be added fills out the rest of the instruction bits.  In that case, the operation does not need to fetch the constant value from a separate location - it 'comes for free' during the 'add' instruction fetch.  Not all constants can be handled in this manner, but a lot of the more common constants can.

Something similar has been done in certain interpreters.  For example, the Pascal P-CODE interpreter implemented each instruction op-code as one byte, but all 128 of the positive byte values were interpreted as immediate loads - e.g if the next op-code was the value 0x40 (the 'space' character), then the value 0x40 was pushed onto the expression stack.  The Java Virtual Machine derives (at least conceptually) from the P-CODE interpreter, and may do the same thing.


How can you construct 3-regular graphs with minimal diameter? Given an even $N$, is it possible to procedurally construct a 3-regular graph $G$ with $N$ vertices such that the maximum distance between any pair of vertexes is the minimum possible for that $N$? I know that a cube, for example, is the solution for $N = 8$, but what about other N's?

The interesting case is connected 3-regular graphs (otherwise the diameter is infinite). We can simply show that if $G$ is such a graph then $D(G)=\Omega\left(\log_2|V|\right)$, where $D(G)$ denotes the diameter of the graph $G$.

Suppose $D(G)=d$. Start at an arbitrary vertex $v\in V$ and begin counting the vertices of the graph by scanning $G$ using BFS originating at $v$. In the first step you encounter 3 vertices ($v$'s neighbors). If at the $i'th$ step you encountered $k$ new vertices, then at the $i+1$ step you will encounter at most $2k$ new vertices (you have three edges to choose from, but at least one will take you back to a vertex you have already met). After at most $d$ steps you will encounter all of $G$'s vertices. This yields the following inequality:

$|V|\le 1+\sum\limits_{i=1}^{d-1}3\cdot 2^{i-1}=1+3\cdot \left(2^{d-1}-1\right)$, hence $d=\Omega\left(\log_2|V|\right)$.

You can see from the above that if $G$ is a connected d-regular graph then $D(G)=\Omega\left(\log_{d-1}G\right)$.

To construct a graph which achieves this lower bound, think about binary trees, and find a way to fix the leaves (and root) in order to achieve 3-regularity.


Explanation for the regular expression for the set of all string over the alphabet {0,1} Why does set of all strings over the alphabet {0,1} is represented by (0+1)*? As per my understanding (0+1) means either 0 and 1 and * means 0 or more occurrence of the given string. Now when we do (0+1)* it looks like we have to select either 0 or 1 and do a * on that so the resulting should be something like

$\{\epsilon,0,1,00,11,000\dots\}$

but why is it following?

$\{\epsilon,0,1,00,01,10,11\dots\}$

It is a Klenee operator and it means all number of $(0 + 1)(0 + 1)\cdots$ with all possible length. As $(0+1)^{10}$ means $(0+1)(0+1)\cdots(0+1)$ for ten times. Hence, All possible combinations of $0$ and $1$ are comming in $(0+1)^*$.

In the other words by the definition, it means the union of all $(0 + 1)^i$ for all $i$ from $0$ to $\infty$.


Are Big-Theta functions asymptotic monotonically non decreasing? For example, suppose $f(n) = \Theta(n^2)$, then does that mean for any sufficiently large $n$, $f(n) \le f(n+1)$? Is it a general case for all Big-Theta?

No, it may not be true.

Consider the following function on $\Bbb N$.

$$f(n)=\begin{cases}
(n+2)^2\quad &\text{when } n \text { is odd,}\\
n^2\quad &\text{when } n \text { is even.}\\
\end{cases}$$

Then $f(n)=\Theta(n^2)$. However, for all odd $n$, $f(n)>f(n+1)$. In fact, $f(n)-f(n+1)\to\infty$ when $n$ goes to $\infty$ along the odd numbers.

Here are two related exercises.

Exercise 1. Give an example of $f(n)=\Theta(n)$ such that $f(n)>f(n+1)$ for infinitely many $n$.

Exercise 2. Let $g(n)\ge0$ be an unbounded function on $\Bbb N$.

Let $h(n)=\Theta(g(n))$. Prove that $h(n)<h(n+1)$ for infinitely many $n$.
Construct $f(n)=\Theta(g(n))$ such that for any number $c$, $f(n)-f(n+1)>c$ for infinitely many $n$.


Natural RE undecidable problems but not Turing-complete The Halting problem is a natural undecidable language which is complete for the set of recursivly enumrable sets. I am interested in undecidable but not Turing-complete language such that we can not reduce the Halting problem to it.

What is the most natural undecidable RE problem which is not Turing-complete?

There indeed are sets that are undecidable but not Turing complete.  However,  I'm not sure there is such a thing as a natural undecidable not Turing complete language.

Emil Post set out on a search for exactly this (See Post's problem) and his research resulted in the Simple sets.  To quote from the Wikipedia article:

  [Its existence] was affirmed by Friedberg and Muchnik in the 1950s using a novel technique called the priority method. They give a construction for a set that is simple (and thus non-recursive), but fails to compute the halting problem.


Recurrence which cannot be analyzed by master theorem Given the following recursion,
$$T(n)=T(\frac{n}{2})+ aT(\frac{n}{4})+n^2, $$
How can I find the minimal value for $a$ such that ${T(n)=ω(n^2)}$?

I tried to do it by tree recursion but  I did not succeed to prove it by this method.

Suppose for simplicity that $n$ is a power of 2. Construct the tree corresponding to the recursion – each vertex is labelled by the current value of $n$, has three children, one of which is a leaf. We assume for now that the tree continues forever. Associate with each edge a weight, which is $1$, $a$, or $1$, depending on which term it corresponds to. The weight of a vertex is the product of all weights in the path from the root to the vertex.

Consider the generating series $$P(x) = \frac{1}{1-x-ax^2} = \sum_{m=0}^\infty (x+ax^2)^m.$$
The coefficient of $x^k$ in $P(x)$ is the total weight of vertices whose label is $n/2^k$. Therefore $\tilde T(n) = n^2 P(1/4)$, where the tilde denotes that there is no base case and the recursion continues forever (we will discuss this later on). Thus $\tilde T(n) = \omega(n^2)$ iff the power series $P(x)$ diverges at $x = 1/4$. This happens if $1/4 + a/4^2 \geq 1$, that is, if $a \geq 12$.

There is a slight problem with this argument, namely the tree doesn't continue forever. However, it is easy to see that all leaves are at depth $\Theta(\log n)$, or more accurately, at depths between $\log_4 n$ and $\log_2 n$ (assuming a base case $T(1) = 1$). This shows that
$$
\sum_{m=0}^{\log_4 n} \left(\frac{1}{4}+\frac{a}{16}\right)^m \leq T(n) \leq
\sum_{m=0}^{\log_2 n} \left(\frac{1}{4}+\frac{a}{16}\right)^m.
$$
When $a < 12$, the preceding argument already shows that $T(n) = \Theta(n^2)$. When $a = 12$, these bounds show that $T(n) = \Theta(n^2 \log n)$. When $a > 12$ these bounds are not enough to determine the asymptotics, though definitely $T(n) = \omega(n^2)$.

The Akra–Bazzi method is a general form of this argument. To solve your recursion, you first have to find the value of $p$ such that $(1/2)^p + a(1/4)^p = 1$. Given that, the Akra–Bazzi theorem tells you that
$$
T(n) = \Theta(n^p) \cdot \left(1 + \int_1^n \frac{u^2 \, du}{u^{p+1}}\right) = \begin{cases} \Theta(n^2) & p < 2, \\ \Theta(n^2\log n) & p = 2, \\ \Theta(n^p) & p > 2. \end{cases}
$$
(I leave the case analysis needed to prove the formula on the right-hand side to you. It is very instructive.)
The critical point is when $p = 2$, and this happens when $1/4 + a/16 = 1$, that is, when $a = 12$, and so in this case $T(n) = \Theta(n^2 \log n)$. When $a < 12$ we have $p < 2$, and so in this case $T(n) = \Theta(n^2)$. These results agree with the calculations above. Finally, when $a > 12$ we have $p > 2$, and so in this case $T(n) = \Theta(n^p)$, the estimate which was too difficult for our crude method above.


Shortest paths in weighted graphs, and minimum spanning trees I stuck in one challenging question, I read on my notes.

  An undirected, weighted, connected graph $G$, (with no negative
  weights and with all weights distinct) is given. We know that, in this graph,
  the shortest path between any two vertices is on the minimum spanning tree (MST). Verify the following:

  1) shortest path between any two vertices $u$, $v$ is unique.

My question is, is this statement (1) is false or True?

Other details is not mentioned in the old exam question, But I think:

1) if this means that for any pair of vertices and for any shortest path between them, it lies on MST So this statement is False. for example Let's assume that we have a graph with two vertices $\{1, 2\}$ and one edge between them with zero weight. There are infinitely many shortest paths between the first and the second vertex ($[1, 2]$, $[1, 2, 1, 2]$, ...)

2) if this means For each $a,b\in V$, for each shortest path $P$ from $a$ to $b$ in $G$ there exists a minimum spanning tree $T$ of $G$ such that $p$ is contained in $T$. this statement is True.

Let's consider the hypothesis of the question to try clarify every aspect:

Our Graph G should:

be undirected
be weighted
be connected
with no negative weights
with all weights distinct
in this graph, the shortest path between any two vertices is on the
minimum spanning tree (MST)

I believe the key point here is the article used in point 6, as pointed out by David Richerby comment

From the wikipedia page: Article (grammar):

Definite Article

  A definite article indicates that its noun is a particular one (or
  ones) identifiable to the listener. It may be something that the
  speaker has already mentioned, or it may be something uniquely
  specified. The definite article in English, for both singular and
  plural nouns, is the.

Indefinite article

  An indefinite article indicates that its noun is not a particular one
  (or ones) identifiable to the listener. It may be something that the
  speaker is mentioning for the first time, or its precise identity may
  be irrelevant or hypothetical, or the speaker may be making a general
  statement about any such thing.

So point 6 lends to some ambiguity:

It could be that the shortest path is implied to be unique. (In
this case I must say the hypothesis and the question are sort of
misleading)
Or it could be that the shortest path is only one of the
possible shortest paths between any two vertices

So if we interpret the hypothesis as per point 1 (i.e. the shortest path means there is a unique shortest path) then the hypothesis is also the answer.

If we interpret the hypothesis as per point 2 then we could consider the following undirected graph:

A--5--B
|   /
2  3
| /
 C

There is no unique shortest path between A and B
Since we could have both:
AB (cost 5)
AC + CB (cost 2+3 = 5)

So if we interpret the hypothesis not meaning the shortest path is unique and asks you to verify this, then we have demonstrated that there is such graph with no unique shortest path that satisfies all other conditions.


What is the complexity of calling a trivial hash function $n$ times? The cost of computing a trivial hash function is effectively zero, so the time complexity is $\mathcal{O}(1)$; however, if I assign $n$ variables using the hash function, is the complexity $\mathcal{O}(n)$.

For example, the pseudo code would look like this:

for i=1 to n
   var[i] = hash[data[i]];
end

The only operation that is being performed is the assignment operation, but in complexity theory, it seems that the assignment operation is not usually included in defining the complexity.

Your question is ill-defined, and it's precisely that that I believe to be your misunderstanding.

There isn't an inherent cost in Landau notation, or any complexity analysis measure for that matter. You first need to define a model, by defining exactly what consists of an operation.

For example you could model only assignments, in which case the complexity is $n$. You could also model only hash function calls, in which case the complexity is also $n$. Or you could consider both to be one unit of time, in which case the complexity is $2n$.

Or perhaps your hash function is $100$ times slower than an assignment, which we assign cost $1$. Then your complexity would be $101n$.


Problems that don't have polykernel when parametrized by vertex cover Are there any problems apart from chromatic number, which is $FPT$ when parametrized by (the size of a minimum) vertex cover, and that does not admit a polykernel when parametrized by (the size of a minimum) vertex cover (under standard complexity assumptions)?

Yes, consider the clique problem (W[1]-hard for the parameter solution size). The problem is FPT when parameterized by the vertex cover number: any clique can contain at most one vertex outside the vertex cover, so it is enough to look at only $2^\tau(n-\tau+1)$ possible solutions, where $\tau$ is the vertex cover number.

On the other hand, the clique problem has no kernel of polynomial size (unless $\text{NP} \subseteq \text{coNP/poly}$). See e.g. the arXiv version

Bodlaender, Hans L., Bart MP Jansen, and Stefan Kratsch. "Cross-composition: A new technique for kernelization lower bounds." arXiv preprint arXiv:1011.4224 (2010).

The same is true for weighted feedback vertex set according to the paper.