Calculate the average length of the linked lists in a hash table I am learning hash tables, and I would like to know how to determine the average length of the linked lists.

For example: A hash table holds about 10,000 employee records. Each record is indexed by the 2-character initials of the employee name, transformed into integers using the mapping: A=01, B=02, C=03, and Z=26. On average no more than 8 comparisons is made every time a search is requested.

How would you determine determine the actual average length of the linked lists, in the hash table, that is pointed to by the hash value slots?

since the hash is constructed such that the input element has an equal chance to be in any of the bins of the hash table, then the average number will be (number of imputed elements) / (size of the hash table)


How to give an approximation algorithm for this unusual bin packing problem? The usual bin packing problem can be formulated as:
\begin{align}
 & \underset{x,y}{\min}
 & & B = \sum_{i=1}^n y_i\\
 & \text{subject to}
 & & B \geq 1,\\
 & & & \sum_{j=1}^n a_j x_{ij} \leq V y_i,\forall i \in \{1,\ldots,n\}\\
    & & & \sum_{i=1}^n x_{ij} = 1,\forall j \in \{1,\ldots,n\}\\
    & & & y_i \in \{0,1\},\forall i \in \{1,\ldots,n\},\\
    & & & x_{ij} \in \{0,1\}, \forall i \in \{1,\ldots,n\}, \, \forall j \in \{1,\ldots,n\},\\
\end{align}

where $y_i = 1$ if bin $i$ is used and $x_{ij} = 1$ if item $j$ is put into bin $i$

I have a similar problem that is formulated as:

\begin{align}
 & \underset{x,y}{\min}
 & & B = \sum_{i=1}^n y_i\\
 & \text{subject to}
 & & B \geq 1,\\
 & & & \sum_{j=1}^n a_{kj} x_{ij} \leq V y_i,\forall i \in \{1,\ldots,n\}, \, \forall k \in \{1,\ldots,n\}\\
    & & & \sum_{i=1}^n x_{ij} = 1,\forall j \in \{1,\ldots,n\}\\
    & & & y_i \in \{0,1\},\forall i \in \{1,\ldots,n\},\\
    & & & x_{ij} \in \{0,1\}, \forall i \in \{1,\ldots,n\}, \, \forall j \in \{1,\ldots,n\},\\
\end{align}

where $y_i = 1$ if bin $i$ is used and $x_{ij} = 1$ if item $j$ is put into bin $i$.

You can see that constraint 2 is no longer the same as in the usual formulation. Now, it must be satisfied for each item $k$.

In my problem the items influence each others (by constraint 2). Each item should be packed into a bin (by constraint 3). The objective is to minimize the number of bins used (by the objective function).

How can I solve this problem? Or how can I design an approximation algorithm for it?

I tired to apply the known approximation algorithm for bin packing such as (Next Fit, First Fit, etc.) but I failed because of constraint 2. (For example, I failed to give a proof of the approximation ratio 2 of Next Fit.)

Could you give me some directions where I should go (e.g., is this problem known) and how to solve this problem?

Your problem is known as Multi-Capacity Bin Packing. One of the foundational papers in the area is by Leinberger, Karypis and Kumar, who state a result of Garey, Graham, Johnson and Yao that in the case of $d$ constraints (in your case, $d = n$) many natural algorithms give a $d+1$-approximation.


Computation of busy beaver function The busy beaver max shifts function, $S(n)$, has known values for $n\leq4$. Is there some basic, structural reason why it's inconceivable that we will ever find $S(n)$ for $n>4$?  What is so different about $n=4$  than $n=5$? Or $n=6$? Somewhere along the way there must be some fundamental difference, otherwise $S(n)$ would be, in principle, computable for all $n$, so what exactly is this difference?

The reason that no program can compute $S(n)$ is that if you knew what $S(n)$ is you could decide the halting problem - you'd know when to stop waiting. On the other hand, for each $m$ there is a program that computes $S(n)$ for all $n \leq m$ - it just uses a table.

If it were possible to prove the value of $S(n)$ for all $n$ (that is, for all $n$ we could prove $S(n) = \alpha$ for some $\alpha$) then we could compute $S(n)$ by searching through all proofs (this assumes that our proof system is valid). So for each proof system there is a minimal value of $n$ for which you cannot prove that $S(n) = \alpha$ for any $\alpha$.

Finally, the reason that we know $S(4)$ is probably because $4$ is a really small number. The number $5$ is slightly bigger, and so things get more complicated. There's no deep reason why we know $S(4)$ but not $S(5)$, just like there is no deep reason why we know the Ramsey number $R(4)$ but not $R(5)$ (though Ramsey numbers are of course computable).


How to know if a code is Huffman or not without having the probability of each codeword? I am new to Huffman coding and I find myself facing a lot of confusion as to how to determine if a code is Huffman or not without having the probabilities associated to each codeword. I know one way is look at whether or not the code is prefix. If not, then it's not a Huffman code. If yes, then we need to check if it gives the shortest possible length, but we don't know the probabilities. How do we ensure the code guarantees the shortest possible length in such case? To illustrate my question, let us look at the following two examples:

Example 1: $\{00,01,10,110\}$
The code is a prefix code, but is the length minimal? I mean it's a bit unusual for me to see Huffman code
for $4$ symbols that does not have one-bit codeword for one of its
symbol (the symbol with highest probability), but them I thought maybe
the first three symbols are equally probable. As such, I tried to find
the Huffman code for $\{0.33,0.33,0.33,0.01\}$ and got
$\{00,01,10,11\}$ with different orders (depending on the usage of
$0,1$ or $1,0$ in the tree). This led me to thinking that the code
under investigation might not be Huffman, yet I am still not sure.
Example 2: $\{01, 10\}$
Again another unusual prefix code as the obvious choice (and the one with minimal length) for two symbols would
be $\{0, 1\}$. But could it be the case that $\{01, 10\}$ can possibly
give a minimal length? I can not see any possible probabilities in
which this is the case, thus I believe this is not a Huffman code.

Am I on the right track? Does there exist an actual method to check whether or nor a code is Huffman without having the probabilities?

If you have a Huffman code, and the codes have lengths $l_i$, then the sum over $2^{-l_i}$ must be equal to 1. In your case, that sum is 1/4 + 1/4 + 1/4 + 1/8 = 7/8 < 1, therefore not a Huffman code. You can replace the code 110 with 11.

(I am quite sure you can prove that for any prefix code, the sum is ≤ 1. And I'm quite sure you can prove that if the sum is less than 1, then there is some bit that you can remove from some code with the code remaining a prefix code, and since there is a finite number of bits to remove, the sum must become 1 eventually).


Is my lambda calculus reduction correct and final form valid in simply typed lambda calc? I'm looking at some lambda calculus at the moment and came across this question:

0:R

1:R

plus: R->R->R

(lambda f:T . lambda g:U . (f 0) (g 0)) (plus 1) (plus (plus 1 1))

Is it well typed given appropriate types for T and U?

I'm new to lambda calc but I gather that we substitute (plus 1) for f and (plus (plus 1 1)) for g.

This will reduce to
(plus 1 0) (plus (plus 1 1) 0)
The right hand side (plus 1 1) will reduce to an R and then we will have (plus R 0) which will reduce to an R. The left side will reduce to an R so the whole expression reduces to the form R R.

Is this correct? Then f and g are of type R -> R (from currying) to make it valid. Is it an issue that the final expression will be of the form R R. Does this mean R gets applied to R then, so R would have to be an 'automorphic' function (mapping from a type to the same type)... is this something related to not having recursion in simply typed lambda calc?

While your way of calculating the types isn't quite how it works, it gives the right answer here. As you say, you end up with f 0 having type R and g 0 having type R. Since we apply f 0 to g 0, R must be of the form R -> X for some X. In other words, you have the equi-recursive type R = R -> X. Such types are almost always disallowed. Thus, this would be a type error. If R is a fixed primitive type, e.g. a type of primitive natural numbers, then it is simply not the case that R = R -> X and so you would also get a type error.


What is a "Master-Reduction"? I keep stumbling upon this term in my lecture notes tutorials and assignments, but I have no clue what it means, google doesnt give me anything usable at all.
Here is an example how this term is used (material in german, but self explanatory really)

So my question is: is this a regional dialect or some important technique that I have missed ?

When proving that a problem is NP-hard, we usually reduce another problem, already known to be NP-hard, to out problem. This process must start somewhere - there must be a first problem which is proven to be NP-hard. For this first problem, say SAT, we need to show that every problem in NP can be reduced to SAT. This is the master reduction, which reduces an arbitrary problem in NP to SAT. Following that, we use reductions that reduce a single problem to the problem at hand.

The name master reduction is perhaps common in Germany, but I have never heard of it. In any case it's just an informal name. Just like the fundamental theorem of algebra is some theorem that somebody at some point decided to call that way, so master reduction is just a term that somebody invented for some reason. I have tried to explain the significance of the term above, but in reality there is no higher significance to the term beyond the particular object it refers to.


Paging - access less than a page of memory I'm having a bit of trouble understanding how less than a page of memory can be used.

From what I understand, memory is given out in page size chunks - say pages are 4096 bytes, and 4 bytes are requested in a program via malloc, can less than a size of a page be allocated? Or is the rest of the memory in the page wasted?

You are confusing paging and memory allocation.

Paging is used to implement virtual memory: Your logical address space is divided into pages, and each page can be mapped to a physical address in RAM, or can be assigned to some location in your backing store. Because the computer has to keep track of how each page is used, we make the pages reasonably large to avoid having an unreasonably large number of pages.

malloc doesn't care about pages at all. It assumes that some portion of your logical address space is available for allocating memory. It doesn't care how this logical address space is mapped to RAM or backing storage. It just takes four bytes from your logical address space and keeps track that this memory is used. If  - by coincidence - all but 100 bytes of a page had been used by malloc (which malloc doesn't know about and doesn't care about), and you called malloc to allocate another 200 bytes, you would likely get the last 100 bytes of that page and the next 100 bytes of the next page. malloc doesn't care.

Paging also doesn't care about malloc, it only cares about reading and writing data.


machine learning classification with financial instrument/time series data I am new to machine learning and have started brainstorming some model ideas that involve financial instrument/time series data. I was thinking it might be useful to use a classification algorithm to predict if an instrument was in fact up or down y% (TRUE/FALSE) after n days, based on i.e. a combination of technical indicator states for each learning example.

That said, in researching the idea I came upon an article that stated training examples in time series data are not independent of each other:

"Time series data has a natural temporal ordering - this differs from typical data mining/machine learning applications where each data point is an independent example of the concept to be learned, and the ordering of data points within a data set does not matter"

My question is as follows: is the above true only if we are trying to predict the continuous value of an asset n days into the future? As far as my idea outlined in the first paragraph is concerned, would this then still be valid considering I am not (apparently) taking into account the specific relationship

Consider that:

a "sliding window" approach can be used with any standard regression / classification algorithm. E.g. given the following time series

Time High Low Open Close Volume
  1   H1   L1  O1   C1     V1
  2   H2   L2  O2   C2     V2
  ...
  i   Hi   Li  Oi   Ci     Vi

you can feed the ML algorithm with these examples:

  O0, H1, L1, O1, C1, V1, H2, L2, O2, C2, V2, H3, L3, O3, C3, V3
  O1, H2, L2, O2, C2, V2, H3, L3, O3, C3, V3, H4, V4, O4, C4, V4
  O2, H3, L3, O3, C3, V3, H4, V4, O4, C4, V4, H5, V5, O5, C5, V5
  ...

(the first value is the target)

The size of the window (s) is an important limitation: the algorithm cannot correlate "candles" that lie more than s timesteps apart.

On the other end, with a large s, all examples appear to be sparse and dissimilar in many ways (see Curse of dimensionality).

You may use other features (e.g. averages, multiple timeframes, Japanese candlestick patterns...) but not without a good knowledge of the specific domain.
ML has tools that, in theory, can deal with timeseries. E.g. Recurrent neural networks can take advantage of their internal memory to process arbitrary sequences of inputs and exhibit dynamic temporal behavior. See Which machine learning algorithms can be used for time series forecasts? for references.


Why do we use the log in gradient-based reinforcement algorithms? I've been reading some papers on reinforcement learning.

$$\Delta w=\frac{\partial ln\ p_w}{\partial w}r$$

I often see expressions, similar to the above one, where the weights (denoted by $w$) are updated following the partial derivative of the policy function (denoted by $p_w$) with respect to its weights.

But why do we take the $\log$? What is its purpose?

We often take the logarithm because:

Maximizing $\log \Phi(x)$ is equivalent to maximizing $\Phi(x)$, so in maximum-likelihood problems, we can maximize the log of the likelihood instead of maximizing the likelihood directly and the result will be equivalent.
The logarithm converts multiplication to addition, and the derivative of a sum is "nicer" than the derivative of a product.  Products often arise when maximizing likelihoods, because the probability of something can often be written as the product of other probabilities   (e.g., when we are calculating the probability of that multiple independent events all happen).  The derivative of the product is ugly, but the derivative of the log of the product is nice and simple.
Gradient descent often involves maximizing a likelihood, so we'll need to take derivatives.  The expressions get simpler/cleaner if we can take the derivative of the log likelihood instead.


Weighted interval set scheduling problem Given a set of weighted intervals, the weighted interval scheduling problem is to select a subset of the intervals such that none of the intervals in the subset overlap and the sum of their weights is maximized. This can be solved in linear time with dynamic programming or memoized recursion.

Is there a version of this problem where intervals are grouped, i.e. interval $a$ can only be in the solution if intervals $b$ and $c$ are also in the solution? By this formulation, there would be a weight associated with each group, or set, of intervals.

The most similar problem I've come across is the exact cover problem, which is NP-Complete, but in this instance we're maximizing weight and all vertices need not be covered.

Any insight will be much appreciated. Thanks!

Sure, you can define any problem you want.  Effectively you would no longer seek a cover of intervals, but a cover of sets, where each set is a union of intervals.  Over a discrete set, any set can be expressed as a union of intervals.  Thus, this is equivalent to the maximum set packing problem.  Consequently, it is NP-hard.


CSP heuristics to help avoid redundancy while checking values for constraint inconsistency? I'm a complete beginner. Please forgive my ignorance.Trying to learn about CSP online, I noticed a lot of the focus on search methods and heuristics which tell you which variable to expand next (e.g. most constrained variable) and those that tell you which value to try first (e.g. least constraining value) but I've yet to see heuristics that relate to constraint checks. Since I'm doing everything by hand, I notice a lot of redundancy when eliminating values from variable domains. How do you go about checking for violated constraints in a way that is efficient? Say constraint A will have me eliminate odd numbers 1 to 1000 and constraint B will have me wipe out everything above 250. Intuitively, it feels like order matters as I would waste my time cherry picking even numbers above 250 to only later find out that anything above 250 was not consistent in the first place. I apologize for lacking the proper terminology, my understanding is mostly intuitive. I hope it makes sense. Thanks in advance! I'm mostly looking to acquire a conceptual understanding of selected topics in computer science so if you have book recommendations or any resource that would be appropriate for me as an interested layman, please don't hesitate!

These are known as variable ordering heuristics.  One standard one is "fail first".  See the "dom" heuristic, i.e., try first the variable with the fewest number of possible values, or "dom+deg", where ties are broken by choosing the variable that participates in the smallest number of constraints.  That would handle the case you list as desired.


How do I tell if a comparison network sorts? I am presented with a comparison network. How can I determine if the comparison network is a sorting network? In the image below there is an example of a selection sort and insertion sort network. The intent is to have a comparison network and sort numeric values. If I test 2^n values in this case 2^8. This is a lot of work|non-efficient way to test it. I'm looking for a mathematical model/proof to verify this is a valid sorting network.

In general, verifying whether a particular comparison network is indeed a correct sorting network is a Co-NP complete problem. If you want to check by testing, then you need to try exponentially many tests.
In particular, there exist sorting networks that sort all but a single value correctly, so you can't hope to test whether the network is correct or not simply by feeding it a few inputs.
One standard method is to test whether it correctly sorts all $2^n$ inputs that are composed solely of zeros and ones.  If it does, then it turns out that it will sort all inputs (even ones that aren't limited to zeros and ones).  However, this requires exponentially many tests.  Moreover, the number of tests cannot be reduced significantly: for zero-one inputs, it is possible to prove that at least $2^n-n-1$ tests are needed, in order to verify that the sorting network is correct.
Alternatively, one can use tests where the inputs are permutations of $1,2,\dots,n$.  This reduces the number of tests needed somewhat, but you still need exponentially many tests.  In particular, $C(n, \lfloor n/2 \rfloor)-1$ tests are necessary and sufficient.
For proofs of these facts, see the following papers:
On the Computational Complexity of Optimal Sorting Network Verification.  Ian Parberry.  Parle'91 Parallel Architectures and Languages Europe, 1991.
Bounds on the size of test sets for sorting and related networks.  Moon Jung Chung and B. Ravikumar.  Discrete Mathematics, vol 81, pp.1--9, April 1990.


Given an input and a program when can you derive the output faster than just running the program? Given an input string W, a description of a turning machine M, and a target output string O (W,M,O) as input, when can a machine M' decide, in fewer steps than simply running M on W, if running M on W, in fact, produces O or not?

What are the circumstances under which this faster M' exists and when is this impossible, i.e. when does this problem reduce to the halting problem (seems like it does)?

Thanks!

Here's an example:

for i from 1 to 10000000000
  do nothing
end for
output 1

In general, however, you can't save much. Indeed, the time hierarchy theorem states, roughly speaking, that you cannot simulate a $T(n)$-time Turing machine running in time $o(T(n)/\log T(n))$.


What kind of Grammar could this be I am trying to sort Grammar into the Chomsky Hierarchy and I can do so for most of my examples but I am stumped by the following one:

bX -> abY

which Type of Grammar would this be, unrestricted grammar, context-sensitive grammar context-free grammar or regular grammar

Thank you for your help

The definition of context-sensitive grammar requires that every production be of the form

$$\alpha A \beta \to \alpha \gamma \beta$$
where $A \in N, \alpha,\beta,\gamma\in (\Sigma\cup N)^* \text{ and } |\gamma| \ge 1$.

Assuming $\Sigma=\{a,b\}$ and $N=\{X,Y\}$, the production $bX\to abY$ does not satisfy this criterion. The only possible decomposition of the left-hand side is $\alpha=b,\beta=\epsilon$, and that doesn't match the right-hand side. So it's not a context-sensitive grammar.

However, that doesn't stop the language generated by that production from being context-sensitive. There is an alternative characterisation of grammars (which is, in fact, often used instead of Chomsky's original context-sensitive criterion), which are the non-contracting grammars. A non-contracting grammar consists only of productions of the form $\alpha\to\beta$ where $\alpha,\beta\in(\Sigma\cup N)^+\text{ and }|\alpha|\le|\beta|$. These grammars are weakly equivalent to context-sensitive grammars; in other words, for any context-sensitive grammar, there exists at least one non-contracting grammar which generates the same language, and vice versa. (This is a weak equivalence because the grammars don't produce the same derivations.) Furthermore, there is a mechanical procedure which can convert a non-contracting grammar into a context-sensitive grammar.

The production you ask about is certainly non-contracting, so (unless other productions in the grammar are contracting) the language is context-sensitive.

If this question appears on a test or class assignment, you should verify which definition of "context-sensitive grammar" your professor uses. Because of they generate exactly the same languages, and because non-contracting grammars are often easier to write, some people use the non-contracting criterion as a definition of "context-free grammar".


Where did Don Knuth say that suffix trees were the "Algorithm of the Year 1973?" If you do a quick search for suffix trees on Google, you'll find a bunch of sources saying that Don Knuth called them the "Algorithm of the Year 1973." However, I can't seem to find a source on this.

Is there a reference to a paper, communication, etc. where Knuth specifically says this about suffix trees?

The source of the quote seems to be From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction by Giegerich and Kurtz.

On page 347, at the start of Section 6 (An Explanation of Weiner's Algorithm), they write

  In this section we go back to the roots
  and take a look at the “Algorithm of the Year 1973” (D. E. Knuth according to [19]).

Reference [19] is an unpublished manuscript:

  [19] V.R. Pratt. Improvements and Applications of the Weiner Repetition Finder. Unpublished manuscript,
  Cambridge, MA, 1973.

Apparently these are lecture notes (this is how they are referred to in the monograph Image and Text Compression by Storer).


Meaning of $\log^{O(1)}(a+b)$ What's the meaning of $\log^{O(1)}(a+b)$ ? Is it simply $(\log_2(a+b))^k$ where k is calculated in constant time ? That is the base 2 logarithm usually in computer science when no other base is set, and the $O(1)$ at the log word means that the whole expression should be raised to the power of that number (which I named k) ?

By definition
$$O(g)=\{f\colon \exists C>0, \exists N \in \mathbb{N}, \forall n> N, f(n)\leqslant C g(n)\}$$
so $O(1)$ can be viewed as set of bounded functions. Outgoing from here $\log^{O(1)}(a+b)$ we can understand as set of functions $\log^{f(n)}(a+b)$ where $f(n) \in O(1)$.
Addition.
Understanding of $f \in \log^{O(1)}(a+b)$ not seems to be differ from understanding of $f \in O(1)$ and does not mean that "O(1) can be arbitrary large constant", as is in your comments. $O(1)$ is not constant, or set of constants, but set of functions. In same way $f \in O(1)$ does not mean that $f$ is bounded by any arbitrary large constant, but there $\exists C_f>0$ for which we have $f(n) \leqslant C_f$. So, $f \in \log^{O(1)}(a+b)$, mean, that $\exists g \in O(1)$, i.e. $\exists C_g>0$ $g(n) \leqslant C_g$, such that $f(n)=\log^{g(n)}(a+b)$. In words: function $f$ is bounded by $\log$ having bounded function in superscript. For example, $f$ cannot be $\log^n(a+b)$, but can be $\log^{\frac{1}{n}}(a+b)$ or $\log^{\frac{1}{n}+1}(a+b)$.


Are there any optimization problems in P whose decision version is hard? Normally to show that an optimization problem is hard, we show the corresponding decision version of the problem is hard. However, is this sufficient to support the conclusion? Does there exist any optimization problem which is easy but its decision version is hard?

No. The optimization problem is "How big is the biggest $X$?" and the decision problem is "Is there an $X$ that is bigger than $y$?" Solving the decision problem simply involves comparing $y$ with the size of the biggest $X$.  You can certainly compare two numbers in polynomial time so, if you can solve the optimization problem (compute the size of the biggest $X$) in polynomial time, you can solve the decision problem.


Time complexity for two multiplications modulo $p$ The time complexity of computing $MK\bmod P$ is $O((\log n)^2)$.  What is the time complexity of computing $MK^2\bmod P$? Is it $O(2(\log n)^2)$ or $O((\log n)^2)$?

$O(2(\log n)^2$ is exactly the same thing as $O((\log n)^2)$. This follows from the definition of $O()$.


Can I assume that L1 is regular? $L_{4},L_{2}$ are regular languages.

given an expression which we know is regular: $L_{4}\cap \bar{L_{2}}\cap \bar{L_{1}}$

May I assume that the language $L_1$ is regular? using closure properties

No, in general. If $\bar{L_2}$ and $L_4$ are both the empty language, or have an empty intersection, then $L_4\cap\bar{L_2}\cap\bar{L_1}$ is regular, but that says nothing about whether $L_1$ is regular.


Sums of all pairs: possible less than quadratic? Is there an algorithm to prepare all sums of pairs of a list ($L$, size $n$, max value $m$) in $< O(n^2)$ such that query "does this sum of pairs exist" takes $< O(n)$?  In other words, can max value $m$ be used to advantage?

E.g. in $L =\{1, 2, 4, 8\}$ and $m = 8$, all (distinct) sums of pairs are $S = \{2, 3, 4, 5, 6, 8, 9, 10, 12, 16\}$ (not given, calculate).

This may be possible using a divide-and-conquer on both $L$ and on the bits of each item.  (N.B. the constraint keeps $S.size$ to $2m$, no need for size $O(n^2)$)

Yes, it is possible using $O(n \log n)$ preprocessing and $O(\log n)$ query time.

Given the set $S$, construct the polynomial $P(x)=\Sigma_{s\in S}\textrm{ } x^s$. Then use the FFT multiplication algorithm to compute $P^2(x)=P(x)*P(x)$ in $O(n \log n)$.

A value $q$ s a sum-of-pairs of $S$ if and only if the coefficient of $x^q$ in $P^2(x)$ is non-zero. Use binary search to look up the coefficient in $O(\log n)$ time ($P^2(x)$ is a polynomial of degree $2m$).

There are also less complicated (and less efficient, but still better than $O(n^2)$) multiplication algorithms that use divide-and-conquer such as Karatsuba multiplication ($O(n^{1.585})$ preprocessing).


Prove that there is no computability reduction HP $\le$ $\Sigma$* I tried to prove in negative way that there is computability reduction  HP $\le$ $\Sigma$* and accept contradiction because of HP $\in$ RE and $\Sigma$* $\in$ R but it feels that is not strong argument.

There is a more solid way to prove it?

Let us actually prove more: If $L$ is a language and $L \not\in \mathsf{R}$, then $L \not\le_\mathrm{T} L'$ for any $L' \in \mathsf{R}$. (Here, $\le_\mathrm{T}$ indicates a Turing reduction; this is synonymous with your notion of a "computability" reduction.) In other words, $\mathsf{R}$ is closed under Turing reductions.

Suppose towards a contradiction that such a reduction exists and is computed by a Turing machine $M$. Furthermore, let $M'$ be a decider for $L'$. Then there is a Turing machine which solves $L$, namely by directly simulating $M$, answering all of its oracle queries by simulating $M'$ on them, and, at the end, answering what $M$ does. This contradicts $L \not\in \textsf{R}$.

The case of the halting problem follows from it not being in $\mathsf{R}$ (since it is not even in $\mathsf{RE}$) and, naturally, $\Sigma^\ast \in \mathsf{R}$.

An aside: If you find the idea of classes closed under Turing reductions interesting, I suggest you look up the computation-theoretical notion of Turing degree. $\mathsf{R}$ would be the "base case" (i.e., degree zero) in that context.


Gödels (first) incompleteness Theorem and the Halting Problem - How limiting is it? When I first heard of these things I was very fascinated as I thought it sets really a limit to mathematics and science in general. But how practically relevant are these things?

For the Halting Problem: Are there more than some artificially constructed cases, where one can't decide whether the algorithm will terminate or not?

For the Incompleteness Theorem: Are there more than some artificially constructed cases, where one can't prove/disprove statement?

I'm asking this because it seems that in most areas of science it doesn't really matter that there are such fundamental limitations. Are they even there? I'd like to know where this really sets a limit and where it is really relevant.

The halting problem being undecidable has lots of practical relevance, here is a quick example:

Writing anti-virus software is hard: We can't decide whether a given piece of code is malicious because if we could we could decide the halting problem.

To see this take a piece of code which takes as input a Turing machine $M$ and an input word $w$ and does something malicious if and only if $M$ halts on input $w$. If we could decide whether a given piece of code were malicious then we could decide whether this piece of code was malicious but then we would be able to decide the halting problem, which we know we cannot do.

What this is saying is that there is no perfect anti-virus software, it can't be done. That doesn't mean we shouldn't try to write anti-virus sotware, just that we will never be able to write a perfect one. In fact any statement about deciding what programs do is undecidable (see  Rice's theorem).

With respect to Godel's theorem, Goodstein's theorem is an example of a statement which is unprovable using the Peano axioms.


Are there things an analog computer can do that digital computing cannot do? The crux of the difference between analog and digital computing is the number of bits of precision available, right? Now, I know that in the Turing machine, numbers can be stored with any degree of precision since the storage medium is an infinite tape.

But in the real world, physical quantities such as energy or position are not incremented in discrete chunks, as they are in their binary. Instead, their exact values can vary continuously as they do in analog circuits.

On that basis then, are there things which, fundamentally, an analog computer can do that digital computing cannot do?

Digital computers are also analog if you get down all the abstraction levels until you reach electrical circuits. The only difference is that we choose to "cut" as with some sort of grid in what levels of detectable analog shifts in signal we create another new abstraction level that we call a bit or a byte.

Anything an analog computer computes, like for example the output signal of an analog filter or the amount of millimeters that a mass in a spring and damper system moves, will also eventually reach a maximum resolution. This is because of for example noise in detectors, error in measuring equipment, and maybe quantum phenomena though I'm not so sure as how that would work. If you define a bit as that very small quantum of information you'll get a digital abstraction for the output of your analog computer.

In other words, if you use a formal abstraction of a digital computer where you can achieve enough resolution for your computations, you'll be able to compute the same than an equivalent real-world analog computer for that problem will compute.

The same problem occurs when digitizing time. For example if you look into analog and digital filter equivalencies, there is always an error that is introduced when digitizing an analog filter. That error tends to 0 as the time step used for the discretizing of the continuous system gets smaller.


How a range query works on a simple B+tree Given a B+tree indexing scheme, wondering how a database actually goes and finds records matching a range query such as the following:

CREATE TABLE foo (
  x int,
  y int
)

SELECT * FROM foo
  WHERE x > 10 AND x < 100
    AND y > 20 AND y < 200

From my understanding this would require 2 b+trees, one for each property ($x$ and $y$). Wondering if one could describe how it would go about about querying the different indexes to satisfy this query. I am having difficulty understanding how the B+tree works in practice.

This is up to the individual database system.  There are multiple ways one might index the data and support this type of query.

One natural approach is that the system might compute in advance an index over the x-values (i.e., a B+ tree that is keyed by the x values) and a second index over the y values (i.e., a B+ tree that is keyed by the y values).  Given those indices, you can now implement the search query by doing a range query on the first B+ tree to find all values where x > 10 AND x < 100, then iterate through them and keep the ones that also satisfy y > 20 AND y < 200.

It is also possible to build multi-dimensional data structures that support 2D range queries, but those are more complex and might not be used in a typical database system.


Computational complexity of maximizing sum of rational functions I have a optimization problem:

$$\max_z\ \sum_{i=1}^n \frac{W_i}{D_i - z_i} \quad \text{s.t.}\ \sum_{i=1}^n z_i \leq k, z_i \in [0,k],$$ where each $W_i$, $D_i$ are constants and $z_i$ are integer variables. Assume each $D_i >k$.

The optimal solution obviously satisfies $\sum_{i=1}^n z_i =k$.
But it seems there is no efficient way to get the optimum other than trying out all partitions.

Also, I know the above problem can be formulated as linear integer programming.

Is there any hint of proving the hardness of the above problem?

Your problem can be solved in polynomial time.

Suppose $n-2$ variables (without loss of generality, say $z_3,\ldots,z_n$) are fixed, then the objective becomes maximizing $$\frac{W_1}{D_1-z_1}+\frac{W_2}{D_2-z_2}$$ where $z_1+z_2\le k-(z_3+\cdots+z_n):=K$. Let $$f(z)=\frac{W_1}{D_1-z}+\frac{W_2}{D_2-(K-z)}, 0\le z\le K,$$
then
$$f''(z)=\frac{2W_1}{(D_1-z)^3}+\frac{2W_2}{(D_2-K+z)^3}\ge0,$$
which means $f(z)$ is convex on $[0,K]$, thus the maximum value is achieved at either $z=0$ or $z=K$. This suggests that we can adjust an optimal solution such that either $z_1=0$ or $z_2=0$.

We can repeat this adjustment until there are only one non-zero variable among $z_1,\ldots,z_n$. So to solve your primary problem, just try the solutions $(k,0,\ldots,0),(0,k,\ldots,0),\ldots,(0,\ldots,0,k)$ and choose the optimal one among them.


Expected Time for LookUpSkipList A skip list

Let C(k) = the expected length of the path that raises k levels backwards.

Thus C(0) = 0

For any node P in the path, with k levels higher to go, there are two cases:

P is a node of level i and proceeds backwards to a node of at least level i and still k levels to go
P is a node at a level higher than i and must yet rise (k-1) levels

Each of these two cases has a probability of 0.5

Why C(k) = 2k and how to interpret this formula? Is the analysis formula in the figure right?

The recurrence can be solved as:
$$
\begin{align}
C(k) &= \frac{1 + C(k)}{2} + \frac{1 + C(k-1)}{2}\\
2 \cdot C(k) &= 1 + C(k) + 1 + C(k-1)\\
C(k) &= 1 + 1 + C(k-1)\\
C(k) &= 2 + C(k-1)\\
\end{align}
$$
Then this can clearly be expanded to a summation:
$$
\begin{align}
C(k) &= 2 + C(k-1)\\
&= 2 + 2 + C(k - 2)\\
&= 2 + 2 + 2 + C(k - 3)\\
& \dots\\
&= 2 + 2 + \dots + C(1)\\
&= 2k\\
\end{align}
$$

I haven't done much investigation into skip lists, but the math you've shown checks out. ✓

EDIT

The reason $C(k)$ appears in the left and right side of the equation, which seems concerning, is because of the Skip List structure. Take this procedure (source) to $find(86)$:

Now let's consider the reverse of this path. Notice we always move up if we can. So for any node in the reverse path, we can either (1) move up or (2) move left:

We move up. Now we have $C(k-1)$ more levels up to go: $$1 + C(k - 1)$$
We move left. We have made no progress upwards, therefore we still have $C(k)$ more levels up to go: $$1 + C(k)$$

For a randomized skip list, either of these scenarios occurs with probability $\frac{1}{2}$. This is how we get the final recurrence:

$$C(k) = \frac{1 + C(k)}{2} + \frac{1 + C(k-1)}{2}$$


3-SAT for variables appearing 3 times I've been trying to investigate 3-SAT for variables appearing 3 times and so far I'm getting some mixed answers as to its complexity.

For example, https://people.maths.ox.ac.uk/scott/Papers/restricted3sat.pdf says

  instances of 3-SAT in which every variable occurs three times are
  always satisfiable (this is an immediate corollary of Hall’s Theorem),
  while it is NP-hard to decide the satisfiability of 3-SAT instances in
  which every variable occurs four times

so apparently when variables appear 3 times it's an easy problem (?).

But the following two references seem to say something else:

From here, http://www.csie.ntu.edu.tw/~lyuu/complexity/2008a/20080403.pdf,

  3sat is NP-complete for expressions in which each variable is
  restricted to appear at most three times, and each literal at most
  twice.

and http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.319.8796&rep=rep1&type=pdf Lemma 5:

  The  SAT-3  problem  is  NP-complete  even  when  each  variable
  appears  3  times.

So is this problem NP-complete for when variables appear 3 times or 4 times? I'm pretty confused.

There is no conflict between your references. The problem is that they have slightly different definitions of what 3-SAT is. You need to read the (original) theorems by Tovey very carefully.

  Let r,s-SAT denote the class of instances with exactly r variables per
  clause and at most s occurrences per variable.

  [...]

  Theorem 2.1. Boolean satisfiability is NP-complete when restricted to instances with 2 or 3 variables per clause and at most 3 occurrences per variable.

  [...]

  Theorem 2.4. Every instance of r,r-SAT is satisfiable.

The reason there's no conflict is that you need to allow 2 or 3 literals per clause to make 3-SAT $NP$-complete when restricted to at most 3 occurrences per variable. The trivially satisfiable bit only kicks in when you have exactly 3 literals per clause and at most 3 occurrences per variable.


Unique decipherability of infinite regular language Can we design an algorithm to test if a infinite regular language is a code?
We have the S-P algorithm to determinate if a finite language is a code. But how about the infinite part of regular languages?
If we have a regex which describes our set of words, then is it possible to modify the S-P algorithm to work on an infinite set without creating Pattern Matching Machines? If it helps, let the regex use only '* | ()' as special symbols.
I thought about making an algorithm which would work based on a PMM, but it isn't as trivial as the S-P algorithm for finite sets, checking the suffixes of strings with matching prefix. The algorithm would be creating a PMM from the regex and traversing it for the search of suffixes etc. like in the S-P algorithm.

McCloskey gave such an algorithm in his paper An $O(n^2)$ Time Algorithm for Deciding
Whether a Regular Language is a Code. Given an NFA on $n$ states, his algorithm runs in time $O(n^2)$. Since a regular expression of length $n$ can be converted to an NFA with $O(n)$ states in linear time, McCloskey's algorithms runs in quadratic time even when given a regular expression as an input.


Rating elements via partial orders I would like to rate a set of $n$ elements, with each element assigned a rating from ${0,\dots, 10}$.

The way in which I want to rate is by repeatedly selecting subsets of $k$ elements and querying a user to rank them relative to each other. I would like a means of minimizing the number of necessary queries to assign ratings (i.e. "how do I pick which elements I should ask about?"), and a way of aggregating my partial orders into the appropriate buckets ("when do I stop, and how do I map the partial order into my range?").

Are there any decent references I should be looking at?

What you're essentially asking is to find a total ordering of a graph of users whose partial orderings are results of querying a user for their relative rank. Your asymptotic complexity of the minimum necessary number of partial orders will relate to the Stirling number of the Second Kind mathworld.wolfram.com/StirlingNumberoftheSecondKind.html. To find this total ordering (re: "how do I map the partial order into my range?") you would topologically sort the graph you're describing. Note that for every vertex, $u\leq_p v\Rightarrow (u,v) \in E$, and the graph would be directed.


Hardness of Approximation of MAX-3SAT This is probably a duplicate of this question, but I need a somewhat blunter answer.  Let's say I have a polynomial time algorithm that finds an assignment that satisfies more than $\frac{7}{8}$ of the clauses of a satisfiable 3SAT instance.  Do I collect my million dollars from the Clay Institute for proving $P=NP$?

I believe that Håstad gave such an algorithm in 2000, see On bounded occurrence constraint satisfaction. His algorithm is stated for instances where each variable occurs at most $B$ times, and the advantage over 7/8 depends on $B$. The running time, however, seems not to depend on $B$.

In order to prove that P=NP, you need to find an algorithm which, given a satisfiable instance, satisfies at least $7/8+\epsilon$ clauses, for some constant $\epsilon>0$. This will enable you to distinguish between satisfiable instances and instances which are at most $7/8+\epsilon/2$ satisfiable, which is NP-hard as my answer to the question you mention shows.


Proof of equivalence of parse-trees and derivations Intuitively, every derivation in a context-free grammar corresponds to a parse-tree and vise versa.

Is this intuition correct? If so how can I formalize and prove such a thing?

Theorem.
Let $G = (V, T, P, S)$ be a Context-free Grammar. Then $\forall A \in V, A \rightarrow^* \alpha \Leftrightarrow \exists$ a parse-tree $T'$ rooted at node $A$ with yield $\alpha \in (V \cup T)^*$.

Meanings of symbols:

$V$ is the set of non-terminals
$T$ is the set of terminals
$P$ is the set of productions
$S \in V$ is a designated start symbol.

A parse-tree $T'$ for a derivation is defined as follows:

The root is labeled with a symbol $\in V$
If $T'$ has a node labeled $A$ whose children are labeled $X_1, X_2, \dots, X_n$ such that $X_i$ is to the left of $X_j$ for all $i \lt j$, then $A \rightarrow X_1X_2\dots X_n$ is a production $\in P$.

proof. We prove $\forall A \in V, A \rightarrow^* \alpha \Rightarrow\exists$ a parse-tree $T'$ rooted at $A$ with yield $\alpha \in (V \cup T)^*$ and vice-versa. We will refer to a node with label $L$ as node $L$.

First we show the ($\Leftarrow$) part.

Assume there is a parse-tree $T'$ rooted at $A$ with yield $\alpha$. If the tree has $1$ internal node, then $A \rightarrow \alpha$ is a production in $P$ (by definition of a parse-tree). Since $A \rightarrow \alpha \Rightarrow A \rightarrow^* \alpha$, we are done.

Assume that the ($\Leftarrow$) part holds for all parse-trees with fewer than $n$ internal nodes (induction hypothesis). If the parse-tree has $n \gt 1$ internal nodes, let $X_i, i = 1, 2, \dots, m$ (be it a non-terminal or a terminal) denote the label of the $i^{th}$ child of the root-node $A$. Each of the $X_i$ nodes has fewer than $n$ nodes. By the induction hypothesis, each of the $X_i$ nodes is the root of a parse-tree with yield $x_i$. Knowing that all the descendants of $X_i$ are to the left of all of the descendants of $X_j$ for all $i < j$, we can write $\alpha = x_1x_2\dots x_m$. $A \rightarrow X_1X_2\dots X_m$ is a production in $P$ and a derivation looks like:  $A \rightarrow X_1X_2\dots X_m \rightarrow^* x_1X_2\dots X_m \rightarrow^* \dots \rightarrow^* x_1x2\dots x_m = \alpha$.

Now we show the ($\Rightarrow$) part.

Assume $A \rightarrow^* \alpha$ for some $A \in V$. If $A \rightarrow \alpha$, then the tree in Fig. 1 is a parse-tree with yield $\alpha$ and we are done.

Assume that the ($\Rightarrow$) part holds for all derivations with fewer than $n$ steps (induction hypothesis). If $A \rightarrow^* \alpha$ is a derivation with $n$ steps, let $A \rightarrow X_1X_2\dots X_n$ be the first step in the derivation-chain. Let $V' = {X_1, X_2, \dots, X_n} \cap V$. Each of the elements of $V'$ derives a sub-string of $\alpha$ with fewer than $n$ steps. By the induction hypothesis, there is a parse-tree rooted at node $V'_i$ with yield $v'_i$. We form a parse tree rooted at $A$ with yield $\alpha$ as follows:

Add a root-node labeled with $A$
Add a link between $A$ and every node labeled with a symbol $\in V'$
Add a link between $A$ and every node labeled with a symbol $\in \{X_1, X_2, \dots, X_n\} \cap T$

This ends the proof.


Proving that $a^{2^kp}$ isn't context-free (where $p$ goes over all primes) I have this language and have to prove that its not context free:

$$L = \{a^{2^kp } \mid k \in \mathbb{N}, p \text{ is prime number}\}.$$

Because it's unary, a context free language is also regular, so it should be enough to prove that this language isn't regular.

Proving $a^p$ and $a^{2^k}$ aren't regular is simple. But how do I prove it with the "product" of these two?

My thought was, because $a^{2^k}$ isn't regular and also not context free,
if $a^{2^k}$ were regular/context free, concatenating this language $p$ times, we would deduce that the above language would also be regular/contextfree, because regular and CFL are closed under concatenation. But because $a^{2^k}$ isn't regular/context free, the $p$-times concatenation of this also isn't regular/context free.

Is my attempt correct?

Your attempt is wrong for several reasons:

If $L$ isn't regular then it doesn't mean that $L^p$ isn't regular. For example, let $L = \{ a^{n^2} : n \geq 0 \}$. Then $L$ isn't regular but $L^4$ is regular.
The language $L^p$ (the concatenation of $p$ copies of $L$) is not the same as the language $\{ w^p : w \in L \}$. For example, $\{a,aa\}^2 = \{a,aa,aaa,aaa\}$ whereas $\{ w^2 : w \in \{a,aa\} \} = \{aa,aaaa\}$.
To obtain your language from $L' = \{ a^{2^n} : n \geq 0 \}$ you will need to take the union of infinitely many powers of $L'$. There is usually very little you can say about infinite unions, since every language can be written as an infinite union of words.

One way to show that your language isn't regular is using the following criterion:

  Suppose that $L = \{ a^i : i \in S \}$ is an infinite regular language. Then $|S \cap \{1,\ldots,n\}|/n$ tends to a positive rational limit.

This criterion follows from the fact that $L$ is regular iff $S$ is eventually periodic.

The Erdős–Kac theorem implies that the fraction of numbers in $\{1,\ldots,n\}$ with at most two distinct prime factors tends to 0. In particular, if $S = \{ 2^k p : k \geq 0, p \text{ prime} \}$ then $|S \cap \{1,\ldots,n\}|/n \longrightarrow 0$. Since $L$ is infinite, the criterion shows that it is not regular.


If all frames are naturally broadcast in a LAN, what is the need for a broadcast address? The Ethernet MAC address FF:FF:FF:FF:FF:FF is reserved for broadcasts. If all frames are naturally broadcast in a LAN, what is the need for a broadcast address?

So that receiving devices can blindly throw away packets that aren't addressed to them or the broadcast address. Doing this test is much simpler than having to verify the CRC and tossing it up to the next layer that may toss it out itself.

A switch will also make use of the target address to only propagate packets to where it knows the destination address resides, reducing congestion.

The broadcast destination is used for stuff like DCHP where the sender doesn't know the target's MAC but still needs to send out the message.


Number of nodes of given height in binary heap Show that there are at most $\lceil n/2^{h+1}\rceil$ nodes of height $h$ in any $n$-element binary heap.

How can I show this? Or, how can I prove this?

Suppose towards a contradiction that your heap $H$ contains at least $\lceil n/2^{h+1} \rceil + 1$ nodes of height $h$, for some choice of $h$.

At least $\lceil n/2^{h+1} \rceil$ of these nodes are the roots of a complete binary subtree of the heap. Therefore each of these subtrees contains $\sum_{i=0}^h 2^i = 2^{h+1}-1$ nodes.

The subtree of $H$ rooted in any of the remaining nodes of height $h$, contains at least $1$ vertex (stronger lower bounds are possible, but this is all we need).

Since the subset of nodes having height at least $h$ in $H$ induces a binary tree $T$ whose leaves are the nodes of height exactly $h$ in $H$, we know that $T'$ must have at least $\lceil n/2^{h+1} \rceil + 1 - 1$ internal nodes.
This means that the number of nodes of height larger than $h$ in $H$ is at least $\lceil n/2^{h+1} \rceil$.

Then, the total number $n$ of nodes in $T$ must be at least:

$$
\begin{align*}
n \ge \lceil n/2^{h+1} \rceil  \cdot (2^{h+1}-1) + \lceil n/2^{h+1} \rceil + 1 =
\lceil n/2^{h+1} \rceil  \cdot 2^{h+1} + 1
\ge n + 1.
\end{align*}
$$

This is a contradiction.


Why are some programming languages "faster" or "slower" than others? I have noticed that some applications or algorithms that are built on a programming language, say C++/Rust run faster or snappier than those built on say, Java/Node.js, running on the same machine. I have a few question regarding this:

Why does this happen?
What governs the "speed" of a programming language?
Has this anything to do with memory management?

I'd really appreciate if someone broke this down for me.

In programming language design and implementation, there is a large number of choices that can affect performance. I'll only mention a few.

Every language ultimately has to be run by executing machine code. A "compiled" language such as C++ is parsed, decoded, and translated to machine code only once, at compile-time. An "interpreted" language, if implemented in a direct way, is decoded at runtime, at every step, every time. That is, every time we run a statement, the intepreter has to check whether that is an if-then-else, or an assignment, etc. and act accordingly. This means that if we loop 100 times, we decode the same code 100 times, wasting time. Fortunately, interpreters often optimize this through e.g. a just-in-time compiling system. (More correctly, there's no such a thing as a "compiled" or "interpreted" language -- it is a property of the implementation, not of the language. Still, each language often has one widespread implementation, only.)

Different compilers/interpreters perform different optimizations.

If the language has automatic memory management, its implementation has to perform garbage collection. This has a runtime cost, but relieves the programmer from an error-prone task.

A language might be closer to the machine, allowing the expert programmer to micro-optimize everything and squeeze more performance out of the CPU. However, it is arguable if this is actually beneficial in practice, since most programmers do not really micro-optimize, and often a good higher level language can be optimized by the compiler better than what the average programmer would do.
(However, sometimes being farther from the machine might have its benefits too! For instance, Haskell is extremely high level, but thanks to its design choices is able to feature very lightweight green threads.)

Static type checking can also help in optimization. In a dynamically typed, interpreted language, every time one computes x - y, the interpreter often has to check whether both x,y are numbers and (e.g.) raise an exception otherwise. This check can be skipped if types were already checked at compile time.

Some languages always report runtime errors in a sane way. If you write a[100] in Java where a has only 20 elements, you get a runtime exception. In C, that would cause undefined behavior, meaning that the program might crash, overwrite some random data in memory, or even perform absolutely anything else (the ISO C standard poses no limits whatsoever). This requires a runtime check, but provides a much nicer semantics to the programmer.

However, keep in mind that, when evaluating a language, performance is not everything. Don't be obsessed about it. It is a common trap to try to micro-optimize everything, and yet fail to spot that an inefficient algorithm/data structure is being used. Knuth once said "premature optimization is the root of all evil".

Don't underestimate how hard it is to write a program right. Often, it can be better to choose a "slower" language which has a more human-friendly semantics. Further, if there are some specific performance critical parts, those can always be implemented in another language. Just as a reference, in the 2016 ICFP programming contest, these were the languages used by the winners:

1   700327  Unagi                       Java,C++,C#,PHP,Haskell
2   268752  天羽々斬                     C++, Ruby, Python, Haskell, Java, JavaScript
3   243456  Cult of the Bound Variable  C++, Standard ML, Python

None of them used a single language.


EXPTIME vs Super-polynomial time It is proven by Time hierarchy theorem that EXPTIME-complete do not belong to P even if we do not know if NP belong to P.

Before I read wiki, I found EXPTIME algorithm for solving 3-sat, the brute algorithm $O(2^n)$. Could I announced then, that there could not be polynomial solution for 3-sat?

Time hierarchy theorem prove that there are EXPTIME problems that are not in P. But how can you prove that problem is EXPTIME and not super-polynomial time?
Also please tell me what is the deference between super-polynomial and polynomial times in context of polynomial expression.

*If you have solution for just one of the questions it's fine.

No, that doesn't prove there's no polynomial time solution for 3-SAT, for a couple of reasons.

Saying that you have an $O(2^n)$ algorithm for something only provides an upper bound. The algorithm takes no more than some constant times $2^n$ steps, for big enough $n$ but I can tell you that I have no more than one trillion dollars in the bank and you still have no idea how wealthy I am.
If your suggested argument was solid, the following would be a direct proof that $\mathrm{P}\neq\mathrm{EXP}$. Here's an exponential-time, brute-force recursive algorithm for graph connectivity: check that every proper subset of the graph's vertices is connected and sends an edge to at least one vertex not in the subset. This can't prove that there's no polynomial time algorithm for graph connectivity because we already know that plenty of those exist. Similarly, observing that you have an exponential-time algorithm for 3-SAT doesn't prove that there isn't also a polynoial one.
$\mathrm{P}\subseteq \mathrm{NP}\subseteq \mathrm{EXP}$ so we already know there is an exponential-time algorithm for every problem in $\mathrm{P}$ and $\mathrm{NP}$. Knowing that 3-SAT is in $\mathrm{EXP}$ tells you nothing new.  However, if you could prove that 3-SAT is $\mathrm{EXP}$-complete, that would prove that $\mathrm{NP}=\mathrm{EXP}$ and, since we know that $\mathrm{P}\neq\mathrm{EXP}$ from the time hierarchy theorem, that would prove $\mathrm{P}\neq\mathrm{NP}$. But it's very unlikely that 3-SAT is $\mathrm{EXP}$-complete. :-)

  [...] how can you prove that problem is EXPTIME and not super-polynomial time?

"Super-polynomial" just means "more than a polynomial". EXPTIME is an example of a super-polynomial time complexity class.

  Also please tell me what is the deference between super-polynomial and polynomial times in context of polynomial expression.

That doesn't make sense. A polynomial is a polynomial so it can be expressed as a polynomial; a function that's super-polynomial isn't a polynomial so it can't be expressed as a polynomial.  I'm not sure why you've latched onto this phrase "polynomial expression".


Why is the A* search heuristic optimal even if it underestimates costs? A* search finds optimal solution to problems as long as the heuristic is admissible which means it never overestimates the cost of the path to the from any given node (and consistent but let us focus on being admissible at the moment).

But why does it always find the optimal solution if the heuristic underestimates? For example, if it underestimates a non optimal path by more than what it underestimates the optimal one, isn't that equivalent to over estimating?

A* maintains a priority queue of options that it's considering, ordered by how good they might be. It keeps searching until it finds a route to the goal that's so good that none of the other options could possibly make it better. How good an alternative might be is based on the heuristic and on actual costs found in the search so far.

If the heuristic underestimates, the other options will look better than they really are. A* thinks those other options might improve the route, so it checks them out. If the heuristic only underestimates by a little bit, maybe some of those routes will turn out to be useful. On the other hand, if the heuristic overestimates, A* can think that the alternatives to the route already has are all terrible, so it won't bother to look at them. But the heuristic overestimates so they might be much better than they seem.

For example, suppose you're trying to drive from Chicago to New York and your heuristic is what your friends think about geography. If your first friend says, "Hey, Boston is close to New York" (underestimating), then you'll waste time looking at routes via Boston.  Before long, you'll realise that any sensible route from Chicago to Boston already gets fairly close to New York before reaching Boston and that actually going via Boston just adds more miles. So you'll stop considering routes via Boston and you'll move on to find the optimal route. Your underestimating friend cost you a bit of planning time but, in the end, you found the right route.

Suppose that another friend says, "Indiana is a million miles from New York!" Nowhere else on earth is more than 13,000 miles from New York so, if you take your friend's advice literally, you won't even consider any route through Indiana. This makes you drive for nearly twice as long and cover 50% more distance. Oops.


How hard are PSPACE-complete problems? There are already good answers from several perspectives regarding the "hardness" of $PSPACE$-complete problems, such as this: What is practical difference between NP and PSPACE-complete?

But what are the practical implications when we actually try to solve (decide) a $PSPACE$-complete problem on a deterministic Turing machine? If $PSPACE \neq NP$ (or $PSPACE \neq P$, should it make a difference) then obviously it will take super-polynomial (exponential?) time. But what about space? Is there some $k>1$ that we know of such that it will definitely take $\Omega(n^k)$ space? And do we know for sure that it won't take more than $O(n^l)$ space for some $l$?

(Or is the question itself stated badly for some reason?)

By definition, PSPACE consists of all languages decided by some Turing machine using polynomial space. So every language in PSPACE can be decided by some Turing machine using space $O(n^\ell)$ for some $\ell$. The space hierarchy theorem ensures moreover that for any $\ell$ there is a language in PSPACE which requires space $\Omega(n^\ell)$.

Any PSPACE-hard language requires space $\Omega(n^k)$ for some $k$, since otherwise any language in PSPACE would be decided by a Turing machine using subpolynomial space, and this contradicts the space hierarchy theorem.

For any $k > 0$ there is a PSPACE-hard language which can be decided in space $O(n^k)$. Indeed, take any PSPACE-complete language $L$. It can be decided using space $O(n^\ell)$ for some $\ell$. Consider now the language $L' = \{(x,0^{|x|^{\ell/k}}) : x \in L\}$, which is PSPACE-hard by reduction from $L$. An algorithm for $L$ can be converted to one for $L'$ which uses $\log n$ space to verify the input structure and $O(|x|^\ell)$ for the rest. Since $n \geq |x|^{\ell/k}$, $O(|x|^\ell) = O(n^{(k/\ell)\ell}) = O(n^k)$.


What are GPU arrays? I came across the Python library libgpuarray and was reading about it but could not really understand what a GPU array is and why do we need it? What is the difference between a normal array and GPU array?

Please excuse the noobness of the question.

Libgpuarray is package (like in proxy or wrapper) around cuda and opencl ndarray - meaning that computation is done on device side (GPU side) as opposed to host side (CPU).
This is described in documentation, and also defined what were the goals of this particular library.

It makes sense to talk about "faster" in terms of GPU if we are having a lot of data, which can be solved on different threads or vectorised (SIMT - new to Flynn taxonomy due to massive parallel but limited computation).

Strictly sequential algorithms benefit nothing, CPU has higher power for them, because GPU cores are slower.
It is not like it is fancy to compute on GPU disregarding problem statement.

On GPU you have smaller and constrainef memory, you have to take bandwidth (sending data from host to device, computation time and sending results from device to host) ti know whether there is speed up or slow down effect on your program.


Convex hull of fixed size I have heard that the quickhull algorithm can be modified if the size of the convex hull (the number of points it consists of) is known beforehand, in which case it will run in linear time. What modifications are required in order to decrease the time complexity of the convex hull algorithm?

It is not true. As you know, we can reduce sorting numbers to finding convex hull (see here). So, we know that size of the convex hull, in this case, is $N$. However, we can't compute convex hull in nearly linear time! as lower bound for sorting numbers in general case is $\Omega(n\log n)$.

Anyhow, we have an algorithm to finding convex hull which is output-sensitive and can be run in $O(n\log h)$, which $h$ is the size of convex hull (see here). Hence, if you know the size of the convex hull such that its size is constant, you can compute convex hull in linear time.


Decidability of fullness of intersection of a CSL with a regular language Let $L_r$ be a regular language with alphabet $\Sigma$ and $L_{\text{csl}}$ be a context sensitive language. Are any of the following questions decidable?

$L_r \cap L_\text{csl} \stackrel{?}{=} L_r$
$\Sigma^* \cap L_\text{csl} \stackrel{?}{=} L_r$
$L_r \cap L_\text{csl} \stackrel{?}{=} \Sigma^*$
$\Sigma^* \cap L_\text{csl} \stackrel{?}{=} \Sigma^*$

I understand that (1) implies the others. I am also looking for any "near variants" that might be decidable.

It is well-known that universality of context-free language is undecidable, making all your items undecidable already for context-free languages, so a fortiori for context sensitive languages (the particular case $L_r=\Sigma^*$ is already undecidable in all items).


How to compress a bit string? I'm aware of some techniques to compress a string of characters such as Huffman coding. I need to know whether there is any technique to compress a long string of arbitrary bits? (ideally with high compression ratio).

Suppose we could always compress a string of length $n$ bits to a string of length $n/2$ bits. Apply this compression algorithm $\log_2 n + 1$ times, and we have reduced a string of length $n$ bits into the empty string. But does the empty string really contain within itself all the information needed to reconstruct the original $n$ bit string?

More generally, a simple counting argument shows that arbitrary strings cannot be compressed. For any compression algorithm $C$:

For every $n$ we can find a string $x$ of length $n$ such that $|C(x)| \geq n$.
For every $n$, at least half the strings of length $n$ satisfy $|C(x)| \geq n-1$.
For every $n$, at least $1-1/n$ of the strings of length $n$ satisfy $|C(x)| \geq n-\log n$.

In particular, an "arbitrary" string cannot be compressed appreciably.

What are compression algorithms good for, then?

Many compression algorithms are lossy, that is, they actually throw away some of the information. This is the case with JPEG, MP3 and MPEG, for example. The compressed picture doesn't look quite the same, but it does look very similar. This property of pictures, that a picture can look similar while differing at the bit level, is exploited by lossy compression algorithms. These algorithms isolate the important parts of the data which are enough to cause in the viewer the same sensation as the original.
Some compression algorithms are lossless but are still able to compress their input. This is because the inputs are often not random and have structure which can be exploited. For example, HTML documents are extremely non-random: for one, they don't use the entire range of characters, but only alphanumeric characters and punctuation. Even raw sound files and pictures can be compressed appreciably, since music and images one would like to compress are not arbitrary white noise, but are smooth in various ways.

After you have compressed a file once, you don't expect it to be compressible again. The aim of a good compression algorithm is to achieve a random looking output, which in particular usually cannot be compressed, as we've seen above.

There are many lossy and lossless compression algorithms out there. If you're looking for lossless compression, you can try some of them out. Many are implemented as standalone tools such as ZIP and BZIP2. Lossy compression strongly depends on the type of medium you are trying to compress. Again, standalone tools are usually available for your perusal.


Fewest induced subgraphs of order <= k which cover every edge I'm facing a graph problem and I'm looking to identify it, maybe as a special case of a more general problem, so that I can then find an approximation algorithm for its solution (I'm assuming it's NP-complete).

I have a graph $G$ with $|V|$ vertices. Every vertex has at least one edge connected to it. I want to find the induced subgraphs of $G$ of order $\leq k$, where every edge in $G$ is found in at least one subgraph and the number of subgraphs is minimized. I can assume as a pre-condition that a solution exists (there exist no cliques with order $>k$).

For example, here is a graph $G$ with 5 vertices. If $k=4$, there's no solution with 1 subgraph since there are more than 4 vertices in $G$. A solution for $k=4$ with 2 subgraphs is shown beside it:

The order of each subgraph can be less than $k$, so $\{\{1, 2, 3\},\{1, 2, 4, 5\}\}$ is another valid solution.

This is not a solution because the black edge between $2$ and $3$ is not covered by either subgraph:

All I'm looking for is a name for the problem, if it exists, so that I can research it and hopefully find an approximation algorithm. Having subgraph order $\leq k$ is a hard requirement but the "minimum number of subgraphs" part can be approximated as long as it's close to minium.

Your problem is known as $k$-clique cover. Goldschmidt, Hochbaum, Hurkens and Yu describe several approximation algorithms in their paper Approximation algorithms for the $k$-clique covering problem. The paper is from 1995, so there are likely newer works on this topic, which you can find by scanning the papers citing this paper.


How to leverage the fact that I'm solving 1000's of very similar SMT instances? I have a core SMT solver problem consisting of 100,000 bit-vector array clauses, and one 10000-dimensional bit-vector array.  Then, my program takes as input k << 100,000 new clauses, and adds them to the core SMT problem.  My goal is, for any input of k clauses, to solve the entire problem.
Is there any static optimization or learning I could do on the core problem in order to find a better way to solve each of its siblings?  For instance, is there some property of the graph of bit-vector variables being constrained in each clause that I could use as a heuristic for solving the specific instances?
Thanks!

Some SAT solvers and SMT solvers offer an interface that lets you push clauses, and then later pop/retract them and push some new ones.  You could explore to see whether this offers a speedup in your situation.  There are no guarantees, and the only way to tell is to try it.


What is the standard notation for introducing syntactical formalism in a paper Suppose you want to introduce a format for a language, commands, ... etc. (Specially in the filed of computer science) in a paper

for example something like below:

X | Y = [ Z ] <W> [ / ] $P

By this, I mean, X or Y could be at the left side of an equation, Z is an optional argument at the right side, <W> is another syntax for something and it is followed by an optional slash and $P is another argument...

What is the standard way to introduce such formalism?

For another example suppose you are

The first one who want to introduce XML synatx
Someone who want to introduce a syntax near or derived from XML

However I am the case two.

There is no general standard way. It depends to some extent on what is
customary in the community you are addressing, on the size and
syntactic complexity of the language you are defining, on the amount
of formality required, and on whether the formalism is intended for
practical use or only for theoretical work.

Typically, if you are defining a programming language, You are likely
to decompose the presentation into a lexical and syntactic part. The
lexical part defines elements of your language such as identifiers and
literals (numbers, strings, or other), usually by means of regular expressions. The syntactic part defines the
various constructs of your language, often with a Context-Free grammar. In the case of programming languages, the most common way of defining a context-free syntax is with the Backus-Naur Form (BNF) which is a metalanguage for syntax definition.

I you a creating a shell command for the Unix system, you will use a
presentation that is quite close to your example.

If you are defining an algebraic formalism, you may define a tree
syntax, or possibly a string syntax based on a context-free formalism,
possibly not caring for syntactic ambiguity issues.

It is up to you to be knowledgeable enough to determine what is
appropriate in your specific case. Existing similar literature should
help you.

Two questions you want to ask yourself when choosing a notation are:

what is sufficient to convey my intent with enough precision, given the purpose and use of the language?
Will it be clear for my readers, given the kind of experience and knowledge they are supposed to have.

Your specific example of being the first to introduce XML syntax, is difficult to answer because the is not really a first. The XML formalism was derived from predecessors such as HTML and SGML, and probably other mark-up languages. One is seldom first, and it is usually wise to restart from the shoulders of those who came before. This applies both to what we define, and to the definitional tools. However, the intended community of users may change, and choices that may be best for a very general public may not be so good for computer specialists, or for theoretical work, the converse being also true. On the other hand, people prefer things close to what they already know.

If you want to introduce a syntax near or derived from XML, the above applies, and you should probably use the same definitional tools But you should probably make sure that your variations are necessary. In such a case, you may also rely on what people may already know of XML, which is fairly widely known, and insist on the differences, on the ways your language departs from XML.


Find string patterns preferably in regex for string streams I am trying to classify the data in a database columns. DB has about 90 million entries.The main goal is to find different patterns in columns to leverage it for create look alike data. The data columns has entries which can easily look like patterns as :

 CUST1212,CUST1213,CUST1214...,  number sequential after CUST
 CODE1213,CODE1242,CODE1289...   random numbers after code
 CUST1213,MUST8324,FIFA12313...
 009-123-2123,003-124-2314,006-213-5322,
 INTER122,INTER222,INTER322...,  number increasing in batch of 100
 OM|ON|TO, IO|OI|UH...,  pipe delimited
 some 6 and 7 digits number.

The issue is there are so many patterns and looks like creating patterns manually based on data is out of option.

I would really appreciate if one can point to how can I build a collection of patterns preferably by usage frequency.

What I started is 1. Segregate the data as per their length as patterns usually generate same string length, sorted them and stored them in different files. 2. Then classifying them further as per Alphabet prefix or numeric prefix. 3. For alpha-prefix segregate further on common alphabets at start.

Now seems I am lost and sincerely hoping if one can point out to me what are my options and probably best to took.

I believe if end of computation if get something like patterns in data and their frequency e.g. CUST[0-9]{4} -> 10k times, [a-zA-Z]{4} -> 50k times [0-9]{3}-[0-9]{3}-[0-9]{4} 10K times etc....., it would be great.

Thanks

The general approach is likely to be:

Identify a set of candidate patterns that might appear.
For each candidate pattern, check for all instances of that pattern.

I'm not aware of any simple procedure that avoids the need for step 1.  The problem is that there are many possible patterns that might appear (e.g., "consists solely of Latin-8 characters"; "length is always at most 100") but most of them won't be meaningful or useful in your domain.  Only you know what will be meaningful/useful.  So, you'll have to use your domain knowledge to identify which potential patterns are useful -- I don't know of any algorithm that can do that for you.


Example of $c^Tx' = c^Tx$ where x is the optimal solution for the linear relaxation (LP) of x' (ILP) I am looking for an example where the optimal solution for the LP problem is equal to the optimal solution of the ILP problem, but the solutions are different.

All I managed to think of was the example of the knapsack problem, when the sum of all the weights were less than W (max weight). However, in this solution x=x', and I was looking for an example in which they are different.

I am a computer science undergraduate so if you have something I may understand it would be much appreciated.

Thank you

Consider any problem in which there are several different solutions, for example MAX-CLIQUE on a graph in which there are several cliques of maximum size. Any convex combination of optimal solutions in another optimal solution which isn't integral.

If the optimum value of the integer program is the same as its linear programming relaxation, then any optimal solution to the integer program is also an optimal solution of the linear program. The problem is that there could be other optimal solutions to the linear program, and an LP solver might find one of them instead of an integral optimal solution. It would be, however, inaccurate to say that the LP and ILP have the same value but not the same solution. Rather, all optimal solutions of the ILP are also optimal solutions of the LP. It's just that the LP has more optimal solutions.


Finding maximally far away points Given a metric space $X$ with finitely many points, and a nonnegative integer $n$, I want to find a set of $n$ points in $X$ which maximizes the minimum distance between any two points.

What algorithms are there to do this?

The problem is NP-hard, by reduction from independent set.

If you have an undirected graph, treat the distance between two vertices $v,w$ to be $2$ if there is an edge $(v,w) \in E$, or $1$ if not.  There there is an independent set of size $n$ in this graph iff there is a set of $n$ points whose minimum distance is 2.

So, your best bet is probably to use some algorithm for independent set (maybe a SAT solver, or maybe something else), combined with a binary search on the minimum distance.


How to handle an undefined case with µ-recursive functions? How to construct my proof and generally what should I aim to get when showing a function is $\mu$-recursive? Should I transform it in some of the basic functions using the given operators?

For example, how should I proceed with the following one:

$\phantom{AAAA}pred(x) = undef$, if $x = 0$
$\phantom{AAAA}pred(x) = x - 1$, if $x > 0$

How should I handle the $undef$-part?

$\mu$-recursive functions are partial functions because of the minimization operator. Without minimization, you get primitive recursive functions, and they're total. So an undefined value can only arise because the minimization operator is involved somehow. For example, you can define
$$\mathrm{undef} := \mu(1)$$
where $1$ is the constant function (with arity $2$) whose value is $1$.

In general, to prove that a function is µ-recursive, you proceed as you would to prove that an object is a member of a class. You demonstrate that the object can be built according to the rules of that class, possibly using objects that other people have already proven to be members.


Is there a formal way of defining a Zeno Machine? The idea of a Zeno machine is pretty interesting to me, but I can't seem to find a formal definition for how a Zeno machine would work.  I can find a couple of definitions around but they are all about the same (I suspect that everyone is cribbing off of each other) and lack any real formalism.  A fairly representative definition is this one from the relevant wikipedium

  More formally, a Zeno machine is a Turing machine that takes $2^{-n}$ units of time to perform its $n$-th step; thus, the first step takes $0.5$ units of time, the second takes $0.25$, the third $0.125$ and so on, so that after one unit of time, a countably infinite (i.e. $\aleph_0$) number of steps will have been performed.

This definitions is a little weird.

The biggest reason this definition is lacking is that the description doesn't really tell us anything about the state of the machine at any time $t \geq 1$.

Now if we look at an example of some psuedo-code for an accelerated Turing machine we have a bit of a conflict. Here is a sample slightly modified from C. Calude, L. Staiger. A Note On Accelerated Turing Machines

begin program
  write 0 on the first position of the output tape
  set i = 1
  begin loop
    simulate the first i steps of T on w
    if T(w) has halted,
    then
      write 1 on the first position of the output tape
    set i = i + 1
  end loop
end program

Now this sample is intended to solve the halting problem on a Turing Machine.  And according to the authors:

  By inspecting the first position of the output tape we need one unit of time to run the above machine in order to decide whether $T(w)$ stops or not

Now here we are relying on some notion of the state of the machine at time $t=1$, which is out of the scope of our definition.

Now the intuitive patch here is to say that the state at time $t=1$ is just the limit of the states as time approaches $1$.[1]  But there are some problems with this the most important being that not all sequences will converge.  Take for example the following pseudo-code:

begin program
  set i = 1
  begin loop
    write i on the first position of the output tape
    if i is 1,
    then
      set i = 0
    else
      set i = 1
  end loop
end program

The sequence of states here cannot converge (regardless of how we choose our metric) and thus this naïve patch does not completely fix the problem.

Is there a way of defining a Zeno machine that is formal and complete?

[1] : In fact while I was putting this question together I found this paper which pretty much outright states this definition.

Hamkins' survey Infinite time Turing machines, linked by Yuval Filmus, formally defines a computational model (Infinite time Turing machine) that meets the requirements of a Zeno machine.
The definition of ITTMs does not use the time based framing; instead it is an extension of classical binary TMs to be defined at transfinite ordinals.  A classical TM has a start status (empty tape, etc.) and a function to get the successive status; a ITTM just adds the status of the machine at limit ordinals.
Rather than taking the limit of the cells in the tape, as suggested and refuted in the question, we take the limit supremum.  Formally for
$$
T(\lambda)_k = \limsup_{n\rightarrow \lambda} T(n)_k
$$
where $\lambda$ is a limit ordinal, $k$ is the index of some cell, and $T$ is the function that gives the tape at some numbered step.
The $\limsup$ ensures that it will always be defined for any sequence (since the alphabet is bounded).  If the normal limit does not converge for some cell then (for a binary alphabet) the cell at time $\lambda$ will be $1$, since in order for it to not converge it must be $1$ at an infinite number of steps.
The state and the location of the read head are resolved much more simply.  Just as there is a start state, there is also a limit state.  At times corresponding to limit ordinals the machine is in the limit state, and the read head is set to the beginning of the tape.

The linked paper does not even mention "Zeno machine" (although it mentions Zeno) and ITTMs may not be the only formal model of a Zeno machine possible (beyond trivial modifications).  However it is a model of computation that allows a Turing machine to perform an infinite number of operations and then continue calculations, so if you are looking for a formal way to talk about Zeno Machines ITTMs work just fine.


Recurrence relation of the coin change problem I'm trying to wrap my head around the coin change problem, where you try to find the total number of ways $N$ cents can be exchanged using $M$ coins $\{C_1, C_2, ..., C_m\}$.

The recurrence relation is this:

I'm having difficulty understanding the 3rd line where it says solution[i][j-v[i-1]]. What exactly is this v they are talking about? I understand it's just the array index above the current one being worked on, but I still don't get what this v is. Can anybody explain please?

For that recurrence to make sense, $V$ can only be the array that contains the coin values; that is, $V=\{C_1, C_2, ..., C_m\}$.

Whenever confronted with a new dynamic programming problem, you should always try to understand how optimal solutions are structured in terms of optimal solutions for smaller subproblems (cf. optimal substructure). This will help you come up with the recurrence relation. Note that, in dynamic programming, you take the solution for one or more subproblems (initially, the base cases) and extend them, repeating this extension iteratively until, eventually, you reach the solution for the original problem.

In the coin change problem (using your notation) a subproblem is of the form solution[i][j], which means: you can make change for $j$ cents using the first $i$ coins from $V$. How have we arrived at this optimal solution (i.e., how have we extended a previously solved subproblem)? We may have brought one more coin from $V$ into the picture. How does this new coin extend the previous solution? Well, there are two possibilities: we have used this coin to make change or we haven't. We must add up these two cases (since both of them represent valid ways to make change):

Case 1 (the coin is not taken): when coin $i$ is not taken, the number of ways to make change for $j$ is exactly the same as it was before coin $i$ was even considered; that is, solution[i-1][j].
Case 2 (the coin is taken): when coin $i$ is taken, your are spending its value; therefore, you must substract the value $C_i$ to $j$. Now, the number of ways to make change is solution[i][j-v[i]] *.

The final recurrence is obtained by adding up these two cases:

solution[i][j] = solution[i-1][j] + solution[i][j-v[i]]

Observe that case 2 is not applicable when $j$ is smaller than the value of the $i$th coin (that is, when $j < C_i$), hence the distinction in the third and fourth lines of your recurrence.

Footnote:

* It will be v[i-1] if the array starts at index 0.


Reduction from Partition problem to 3-Partition problem I'm trying to show how to reduce the Partition problem to the 3-Partition problem.
I'll first describe the problem using the definitions and notations I'm familiar with (I hope they're legit), and will then ask my question.
So, the Partition problem is as follow:
Given a multiset of integers $X$, we have to decide whether or not $X$ can be partitioned into two sub-sets $A,B$ such that $\sum_{x_i\in A}x_i=\sum_{x_i\in B}x_i$.
In the 3-Partition problem, given a multiset of integers $Y$, we have to decide whether or not $Y$ can be partitioned into three sub-sets $A,B,C$ such that $\sum_{x_i\in A}x_i=\sum_{x_i\in B}x_i=\sum_{x_i\in C}x_i$.

I want to show a reduction $Partition\leq _p 3Partition$,
That is, to show that given $X$ as input for the Partition problem, I can build $Y$ as input for the 3-Partition problem, s.t. $X$ can be partitioned to two iff $Y$ can be partitioned to three.
So given $X$, let $\sum_{x_i\in X}x_i=m$, and define $Y$ as:
$Y=\left \{ x_1, x_2,...,x_n,\frac{m}{2}|x_i\in X \right \}$.

Proof:
The first direction is easy: suppose that $X$ can be partitioned to two sub-sets $A,B$ s.t. the above conditions hold, then $Y$ can be partitioned to three: $A,B,C$, while $C=\left \{\frac{m}{2} \right \}$.
I'm stuck with the second direction: suppose that $Y$ can be partitioned to three, why does that guarantee that $X$ can be partitioned to two?

b.t.w, how can I be sure that $\frac{m}{2}$ is an integer? do I even have to pay attention to it?

To answer your bolded question: The sum of the numbers in $Y$ is $\frac{3m}2$. Thus $A$, $B$, and $C$ each need to be of size $\frac m2$. This can only be achieved by partioning as in the first direction.

Regarding your second question: You can not be sure that $\frac m2$ is an integer and you have to pay attention to it, in order to get a formally correct reduction.

The easiest way to address this is by having your reduction function distinguish two cases: If $\frac m2$ is an integer, it proceeds as you describe. If $\frac m2$ is not an integer, it exploits the fact that in this case the answer to the original question ("Can $X$ be partitioned?") is easy. I'll leave it as an exercise to figure out the details of this case.


What time complexity is more significant? A certain algorithm executes $n$ operations of three types: insert, delete, and find.
We know that $n/10$ of the operations are inserts, and the rest are deletes and finds.

You are given two implementations of the algorithm. The first one implements insert in worst case $\Theta(n)$, and the amortized cost of every operation (including insert) is $\Theta(1)$. The second implementation implements insert in worst case $\Theta(\log n)$, and the amortized cost of every operation (including insert) is $\Theta(\log n)$.

Which implementation would you recommend, and why?

You are asking for a practical answer, so you need a practical problem.

State your practical problem. Then examine what would be the effect of using one implementation vs. the other. Based on this examination, you can choose which implementation is more acceptable to you.


Does this constraint satisfaction problem have a name I've been struggling with a particular constraint satisfaction problem, that appears like it should have an easy solution. In fact, I need a very fast solution.

The problem is: I am making a card-playing AI, and at some point I need to guess a plausible solution to the other players hands. Given the history of the game, I can definitely say that some players don't have certain cards .

Put formally: I have a set of elements $S$ (the remaining cards in the game), and the goal is to partition $S$ into a fixed number of disjoint subsets $S_i$, for  $ i \in \{1...n\}$. For each subset, we have a set of elements $A_i$ that they may not have, and a number of elements $N_i$ that this subset must contain. Also, $|S| = \Sigma_i N_i$. Find a partition.

There are a number of extra conditions that could make this problem much easier:

The initial conditions guarantee that there will always be a solution.
All remaining cards are in other peoples hands. There is no deck, and so all other cards have either already been played, or are in my AI's hand.
The number of cards to be distributed is $<24$.
There is always exactly 3 opposing players, i.e. $n = 3$.
For any $i, j$, $abs(|N_i| - |N_j|) <= 1$.

I am convinced that this problem has already been studied and has a name. Does anybody know if it exists? If not, is the problem is simple enough that there is a solution that does not require exponential search?

This is a special case of perfect matching in bipartite graphs and could be solved using standard algorithms for that problem  (e.g., the Hungarian algorithm). It is not the perfect matching problem (it looks easier; and it is much more specific), but it is a special case of it.


Should I keep a relevant constant in the Time Complexity? I designed an algorithm, and the Time Analysis provided next time complexity:

$\mathcal{O}(2^p \cdot (\frac{t}{2}/2^p) \cdot \frac{n}{4})$

what must be simplified to:

$\mathcal{O}(2^p \cdot \frac{n^2}{16})$ = $\mathcal{O}(2^p \cdot n^2)$

That constant factor is quite relevant in this case, and the only reason I'm considering keeping it, is because represents an important fact of the algorithm behavior.

In asymptotic notation constant factors are "modded out". For example, an algorithm runs in time $O(n)$ iff it runs in time $O(2n)$ iff it runs in time $O(n/2)$.

If you want to capture such a difference meaningfully, you have (at least) two options:

Add another parameter. There could be a parameter $t$ such that your algorithm runs in time $O(tn)$. One way to think about it is that the algorithm runs in time $O_t(n)$, i.e., with a big O constant that depends on $t$, and the dependence on the big O constant on $t$ is $O(t)$.
Count a specific operation. In some cases you might be able to count a specific type of operation more accurately. For example, perhaps one sorting algorithm performs $(2 \pm o(1)) n\log n$ comparisons on average, and another performs $(3 \pm o(1)) n\log n$ comparisons on average.


Regarding to the speed of supercomputer There seems to be a sense of competition in creating the fastest computer in the world, and I feel like technically you just have to continue increasing the core number to gain more flops, which is exactly what some countries are doing, so how would you really bench mark the technological level of a supercomputer

for example

United States currently have two supercomputer on the top list with similar performance, however one has significantly less core than the other

Titan     has 560000 cores    17590 Rmax Tflops   with   8000 kW of power

Sequoia   has 1570000 cores   17173 Rmax Tflops   with   7800 kW of power

Does this mean that Titan is a much superior supercomputer than Sequoia as it only uses 1/3 of cores to reach a similar performance, and if it does, this will also imply that judging supercomputer by flops is completely meaningless?

Is there something I am missing here? Such as the increasing complexity of software as the amount of core gets larger and the synchronization of overhead to assign task to each core gets more sophisticated?

Any info would be much appreciated

The only thing you are missing is the importance of the interconnect between cores/processors/racks and the design of the memory system for each processor.

I assume you are referring to the most recent top-500 supercomputer list.  That list is sorted by Rmax, not Rpeak.

Rpeak is a measure of the theoretical maximum number of floating point operations that the system can perform.  For Rpeak you are correct: just add more cores (or more vector units per core) and the Rpeak number will go up.

Rmax is (arguably) a little bit more meaningful.  It is the maximal rate at which the system can run the Linpack benchmark.  The Linpack benchmark requires the system to solve a huge, dense, system of linear equations using LU factorization with partial pivoting in double precision.

For solving a dense system of linear equations you need to carefully partition the problem among the cores, and there needs to be an efficient way for the cores to communicate results back and forth.  So a big part of designing a computer that will get onto the Top500 list is careful design of the interconnect and the software used to send messages between processors.

On the top500 list they tell you what interconnect each system is using. Note that you don't find a system with Ethernet until you get to number 49.  The first 48 all have infiniband, cray gemini or custom interconnects.

There is also a green500 list that measures the MFLOPS/Watt of systems while solving the Linpack benchmark.  The difference between the top system and the 500th system on that list (from last November) is a factor of 75x.

Most people agree that there is a lot more that you want from a supercomputer in addition to being able to efficiently solve massive dense systems of linear equations.  Jack Dongara (who originated the Linpack benchmark) has recently released a paper proposing a new benchmark that measures the speed at which a system can solve a sparse linear system.  http://www.netlib.org/utk/people/JackDongarra/PAPERS/HPCG-Benchmark-utk.pdf.


Asymptotic analysis for quicksort on special case I have the following problem for homework:

Given an array of the form  $[m+1, m+2,..., n, 1, 2,..., m]$ as an input,
analyze quicksort's run time complexity.
TIP: check for $m > \frac{n}{2}$  and  $m \le \frac{n}{2}$

The quicksort algorithm is the deterministic version from CLRS.

I have a sense of what's going on but I'm having trouble proving it properly.

I arrived at the following formula:
$$\begin{align*}
    T(n, m) &= T(n-m, m) + \theta (m^2) + \theta (n) \\
            &= \cdots \\
            &= T(n-(i+1)m, m) + i\theta(m^2) + \sum_{k=0}^{i} \theta(n-km)
\end{align*}$$ from the following reasoning:

at each "step" $i$ the partition will swap the $m$ smallest numbers (located at the end of the sub-array)  with the next $m$ smallest numbers (located at the beginning of the sub-array), keeping their sorted order.
The sub array is of size $n-im$, so the partition takes $\theta(n-im)$.
Then perform the first recursive call on the $m-1$ smallest numbers on the left of the sub-array for ~$\theta(m^2)$.
Next we perform the next recursive call on an sub-array of size $(n-(i+1)m)$.

We can easily see when this will end with a mod operation.
(I understand there is a bit additional work even after we can't sub $m$ smallest numbers anymore but that's not very important so omitted).

Now, my issues are:

I don't understand how to treat $m$ and $n$. $m$ is somewhat dependent on $n$ because it cannot grow indefinitely without $n$ growing as well. But on the other hand, it doesn't depend directly on $n$.
If I substitute the end condition I get an expression with both $n$ and $m$ which I believe I should find a way to express in terms of $n$ alone but I don't know how.

I know I omitted alot of reasoning, details and formalism but it's got quite long anyhow so I hope it's clear enough.
If not, I will be more than happy to clarify.

I'd appreciate any help or suggestions.

EDIT: here is the pseudocode for partition and quicksort:

Partition: http://qph.is.quoracdn.net/main-qimg-65c54b3e9b6fef01a5ff7543ed3a3092?convert_to_webp=true
Quicksort: http://www2.hawaii.edu/~suthers/courses/ics311s14/Notes/Topic-10/pseudocode-quicksort.jpg

A more correct recurrence is
$$T(n,m) = \begin{cases} T(n-m,m) + \Theta(m^2+n) & m \leq n/2, \\ \Theta(m^2+n) & m > n/2. \end{cases}$$
In order to solve the recurrence, let us assume that the hidden constants are all $1$, and that $n = km$. Then
$$
\begin{align*}
T(km,m) &= T((k-1)m,m) + m^2 + km \\
&= T((k-2)m,m) + 2m^2 + km + (k-1)m \\
&= \cdots \\
&= T(m,m) + (k-1)m^2 + km + \cdots + 2m \\
&= km^2 + km + \cdots + m \\
&= km^2 + \frac{1}{2}k(k-1)m \\
&= \Theta(km^2 + k^2m).
\end{align*}
$$
Substituting $k = n/m$ and hoping for the best, we get
$$ T(n,m) = \Theta(nm + n^2/m). $$
This quantity ranges from $\Theta(n^{3/2})$ to $\Theta(n^2)$.