Clarification on evenly dispersing modular hashing I'm going over "Algorithms fourth edition" by Robert Sedgewick and Kevin Wayne.
In the chapter on hash tables I have encountered an easy hashing method called "modular hashing"
hash = k % m

Where k is the key and m - 1 is the size of array (minus 1) that stores the values. Authors suggest to use primary numbers for m because:

If m is not prime, it may be the case that not all of the bits of the key play a role, which amounts to missing an opportunity to disperse the values evenly.

I get why non-primary numbers might be a bad m. If we take a look at m = 10 and k = {17,27,37...}. They will all produce hash equal to 7.
However, I'm not entirely sure as to why primary numbers are superior alternative.
Is it because primary numbers are (due to their definition) never a divisor to the keys that we want to hash (ignoring instances where key=m)?

The remark is quite cryptic. If $m = 2^r$, then only $r$ bits of the input affect the value of the hash. But it any other circumstance, all input bits affect the value of the hash.
By the way, your example ($7,17,27,37$ all get mapped to the same value modulo $10$) works for any value of $m$. For example, $7,18,29,50$ all map to the same value modulo the prime $11$.


Why is my own implementation of Bubble Sort so much slower than another one I found online? I wrote my implementation of Bubble Sort according to my understanding of the general principle of how the algorithm works, and then compared it against another implementation I found online.

def my_bubble_sort(n):
    switched = True
    while switched:
        switched = False
        for i in range(1, len(n)):
            if n[i] < n[i - 1]:
                switched = True
                n[i - 1], n[i] = n[i], n[i - 1]
    return n

def some_other_bubble_sort(n):
    for i in range(len(n) - 1):
        for j in range(len(n) - 1 - i):
            if n[j] > n[j + 1]:
                n[j], n[j + 1] = n[j + 1], n[j]
    return n

While my_bubble_sort() is much faster on processing lists that are already sorted, some_other_bubble_sort() is almost three times faster (= takes 35% of the time) compared to my_bubble_sort() on actually random, unsorted lists.

I'm not sure why that is. Can anyone help me understand?

It can't be the additional checks against switched that make my implementation that much slower, can it?

Pastebin link

I also found that my version seems to be fairly close to the one taught at this MIT lecture.

Which one is generally preferable? Are they both valid implementations of bubble sort? Or is either of the two technically another sorting algorithm?

And which one would be preferable, generally speaking?

From your pastebin, here is the first place you go wrong:

unsorted1 = unsorted2 = [randint(1, 99) for _ in range(count)][:]

Here you assign unsorted1 and unsorted2 to point to the same list. So when you call some_other_bubble_sort on unsorted2, it is in fact no longer shuffled! It is sorted.

The solution is to first assign unsorted1 and then unsorted2 to a copy:

unsorted1 = [randint(1, 99) for _ in range(count)]
unsorted2 = unsorted1[:]

That makes your algorithm only slightly less than twice as slow. That can be explained simply by the fact your implementation does a lot more stuff. In Python the little things add up, like setting switched to True every iteration.


Set notation of the set of all strings How do I present the complement using set notation?

I guess it has to be shows with universal set - {aa,bb} but I do not know how to represent the universal set in terms of set notation. Since, the strings of the universal set can be anything over alphabets {a,b}. So, how to represent it?
I guess something like this might work if we are going from outside to inside {{{a,b}*}*}.
Any help is appreciated.

The universe here is the set of all strings over the alphabet $\{a,b\}$ and is usually denoted by $\{a,b\}^*$.

You have way too many brackets.


Synchronizing speech and text I have a text and a narration of the exact same text. What is the best way to synchronize them together? By synchronizing I mean, finding out for example the location of each word in the audio. For example if the sentence is "I took a cab" I want for markers on the accompanying audio which indicate start of each word.

Obviously any speech-to-text algorithm can be applied here, but given the fact that we've already know the text, I wonder if there's an algorithm for this simplified problem which works either much faster, or gives much better performance. Or if there is a general algorithm that can be tuned for this specific problem.

Papers on algorithms:

A RECURSIVE ALGORITHM FOR THE FORCED ALIGNMENT OF VERY LONG AUDIO SEGMENTS
Pedro J. Moreno, Chris Joerg, Jean-Manuel Van Thong and Oren Glickman
Automatic Alignment and Error Correction
of Human Generated Transcripts for Long Speech Recordings
Timothy J. Hazen
SailAlign: Robust long speech-text alignment
Authors Katsamanis, Athanasios
Black, Matthew
Georgiou, Panayiotis
Goldstein, Louis
Narayanan, Shrikanth S.

Implementations:

Sphinx4 long audio aligner
Sail align
Gentle forced aligner


Human brain vs computer I am looking for a problem that can not be solved by computer but can be solved by human while computer can verify if the answer is correct or not. In fact what is the question in my head is that is there a way to clearly show the smartness in human brain compared to huge computation power of the processors.

We know that there are problems (like the halting problem) that absolutely cannot be solved by a computer because there is no algorithmic solution. But a human cannot solve those problems either.

We also know that there are problems that humans can solve, but which we do not know how to solve with a computer with our current state of knowledge and technology. Problems in image processing ("is there a teddy bear in this picture ?") or natural language processing ("do these two English sentences have equivalent meanings ?") fall into this category. The difficulty here is showing that any of these problems absolutely cannot ever be solved by a computer, given a clever enough program and enough processing power and time - it is not at all clear how you could establish that.

We do not know of any problem that can be solved by a human and absolutely cannot ever be solved by a computer, no matter how powerful.


What is the best of given hashfunctions? In our exam on algorithms there was a question, where given 3 hashfunctions we had to chose one and explain why it's the best.

h_1(x,i)=(x+5*i) mod 1000
h_2(x,i)=(x+17*i) mod 1000
h_3(x,i)=(x+32*i) mod 1000

I am really unsure about this, but I suspect that it is the second one, because it can "hit" more values. If I choose the first one for example, I will be hitting the same buckets over and over (if they are full). Question seems quite simple but my math lecture on this has been a long time ago.

The question is not well-defined, since its unclear what you mean by "best".

I suspect that the intended answer is what you said and that you are using open addressing. Then, for a given $x$, $h_2$ would eventually return all possible values in $\{0, \dots, 999\}$ (since $17$ and $1000$ are coprime). $h_1$ would only return $\frac{1000}{5} = 200$ distinct values, and $h_3$ would only return $\frac{1000}{\textrm{gcd}(32,1000)} = \frac{1000}{8}=125$ distinct values.


Asymptotic Analysis for two variables? How is asymptotic analysis (big o, little o, big theta, big theta etc.) defined for functions with multiple variables?

I know that the Wikipedia article has a section on it, but it uses a lot of mathematical notation which I am unfamiliar with it. I also found the following paper: http://people.cis.ksu.edu/~rhowell/asymptotic.pdf However the paper is very long and provides a complete analysis of asymptotic analysis rather than just giving a definition. Again the frequent usage of mathematical notation made it very hard to understand.

Could someone provide a definition of asymptotic analysis without the complex mathematical notation?

Asymptotic notation for multivariable functions is defined analogously to its single variable counterpart. In the single variable case, we say that $f(n) \in O(g(n))$ if and only if there exists constants $C,N$ such that for all $n > N$ we have  $f(n) \leq Cg(n)$. In other words $f(n)$ is upper bounded by some multiple of $g(n)$ for all $n$ larger than some fixed $N$.

In the multivariate case, the definition is nearly the same, except you have a few more variables to worry about. Let's suppose $f(n,m)$ is a function of two variables. We want to bound $f$ from above by another function of two variables. So we say that $f(n,m) \in O(g(n,m))$ if and only if there exists constants $C,N$ such that for all $n>N$ and $m>N$ we have $f(n,m) \leq Cg(n,m)$. The definition is nearly exactly the same, except now all of our variables must be greater than our fixed constant $N$.

The wikipedia article used $\overrightarrow{x}$ to mean a vector in $\mathbb{R}^d$ which would mean that $f$ and $g$ were multivariable functions of $d$ variables (i.e. $f,g:\mathbb{R}^d \rightarrow \mathbb{R}$). Saying that $x_i > N$ for all $i$ meant that each component of $\overrightarrow{x}$ had to be greater than $N$.


Is there a point to an all-encompassing programming language? There are many programming languages in use throughout the world today, including languages that specialize in database manipulation, functionality, object-orientation, concurrency, etc. Would there be any point in making a language that could do all these things very well, or is it best to keep these languages separate to some degree?

The reason I ask is because I had been interested in building a very basic compiler. As I became more familiar with the concepts behind compilers and the hurdles and obstacles to overcome, I realized that I should probably come up with a language that had some sort of goal. I spoke with a friend about a language that could "do it all", and he said that there was simply no point. I am still confused as to why he might claim this.

You can make a language that does all these things. The problem is that it won't be able to do all these things well, because they're contradictory. For example, database manipulation is fundamentally about changing the state of the system, so it's directly opposed to purely functional programming¹. So is fault tolerance, where a program that's running code that's mathematically proven to terminate might actually fail to terminate because the machine crashes. Object orientation with the hiding of implementation-specific details is opposed to structural polymorphism where a function might inspect the state of its arguments and expects to know about all the ways in which an object can be built. Having static type guarantees is opposed to dynamic type analysis. A language can't provide safe memory accesses and precise memory management in all cases. And so on.

The best you can expect is a “kitchen sink” language that includes all the features that the designers thought of. The thing is, to effectively use some of the features, the programmer needs to restrict themselves to a subset of the language that copes with those features. Of the languages commonly used in industry, C++ is the most kitchen-sinky, and that makes it hard to use because you can never be sure what features a piece of code uses and what assumptions you can make on that piece of code. For example, the type of a Haskell function makes it apparent whether it has a side effect; the type of a Rust function makes its memory management behavior apparent; with C++, you have to look at the documentation and hope that it tells you what you need.

With a kitchen sink language, you really have multiple languages in one, without the benefit of a clear barrier between the languages. Multiple languages that are each good at their job works better.

¹  If you put the database state in a monad, like Haskell does, you're no longer doing purely functional programming. You're doing imperative programming with a type system that models the impurity.


Genetic Algorithms - Why wouldn't we use the principle of Elitism? In Genetic Algorithms, the idea of elitism is that we keep our best solution from the generation in our population regardless of what happens throughout the iteration. However, elitism seems to be discussed as an optional thing; so what situations is using elitism actually a negative aspect of a genetic algorithm?

It increases the convergence speed of the GA, which is a double-edged sword. You want the algorithm to find good solutions quickly, but not so quickly that is has not been able to sample sufficiently large areas of the space that it's not just doing a very local search around the initial population.

Another option that can work well is to be elitist, but try to intelligently figure out when you've converged and should introduce some diversity.


If there is no Hamiltonian path in a DAG then there are at least two different Topological sorts I understand the concept that if there is no Hamiltonian path so there will be 2 smaller paths and with them I can build more then one topological sort but I am not sure how make it formal.
Can you help me to structure the proof?

Let's call two vertices $u$ and $v$ comparable if there is an oriented path from $u$ to $v$ or from $v$ to $u$, and call them incomparable otherwise. Now let's prove that if there is no Hamiltonian path in DAG then there exist two incomparable vertices. Let's use a proof by contradiction and prove instead that if all vertices in a given DAG are pairwise comparable then there exists a Hamiltonian path. Let's prove it by induction by a number of vertices. Obviously, this statement is true for $1$ and $2$ vertex DAGs. Not let's consider an arbitrary DAG where all vertices are pairwise comparable. There is exactly one vertex with zero in-degree in such graph. Let's call this zero in-degree vertex $a$. What is more, if you remove vertex $a$ from your DAG, the remaining subgraph will also be a DAG where every two vertices are comparable. By induction assumption you can build a Hamiltonian path $P$ in this subgraph. Let's call the first vertex of this Hamiltonian path $v$. Then there is an edge $(a, v)$ in the original DAG. Indeed, let's assume that such edge does not exist. But we know that there is a path from $a$ to $v$ (because they are comparable and there is no in-edges to $a$). Let $b$ be the second vertex of the path from $a$ to $v$. Then there is a path from $b$ to $v$, but there is also a path from $v$ to $b$ (by construction of $v$). Hence, there is a cycle in a considered graph. Contradiction. So there is an edge $(a, v)$ and $v$ is a start vertex of some Hamiltonian path $P$ in the subgraph without $a$. Thus $\{a\} \cup P$ is a Hamiltionian path in the original graph.
So in every DAG without a Hamiltonian path there is at least 2 incomparable vertices. Thus you can get two different topological sortings just by swapping the numerations on dfs subtrees of these two vertices.


Are algorithms (and efficiency in general) getting less important? Since buying computation power is much affordable than in the past, are the knowledge of algorithms and being efficient getting less important? It's clear that you would want to avoid an infinite loop, so, not everything goes. But if you have better hardware, could you have somehow worse software?

On the contrary. At the same time that hardware is getting cheaper, several other developments take place.

First, the amount of data to be processed is growing exponentially. This has led to the study of quasilinear time algorithms, and the area of big data. Think for example about search engines - they have to handle large volumes of queries, process large amounts of data, and do it quickly. Algorithms are more important than ever.

Second, the area of machine learning is growing strong, and full of algorithms (albeit of a different kind than what you learn in your BA). The area is thriving, and every so often a truly new algorithm is invented, and improves performance significantly.

Third, distributed algorithms have become more important, since we are hitting a roadblock in increasing CPU processing speed. Nowadays computing power is being increased by parallelizing, and that involves dedicated algorithms.

Fourth, to counterbalance the increasing power of CPUs, modern programming paradigms employ virtual machine methods to combat security loopholes. That slows these programs down by an appreciable factor. Adding to the conundrum, your operating system is investing more CPU time on bells and whistles, leaving less CPU time for your actual programs, which could include CPU-intensive algorithms such as video compression and decompression. So while hardware is faster, it's not used as efficiently.

Summarizing, efficient algorithms are necessary to handle large amounts of data; new kinds of algorithms are popping up in the area of artificial intelligence; distributed algorithms are coming into focus; and CPU power is harnessed less efficiently for various reasons (but mainly, because computers are getting more powerful). Algorithms are not dead yet.


Seeking Efficient Approximation Algorithm for Adaptation of TSP Consider the following adaptation of the traveling salesman problem:

  Given a complete, undirected graph $G$ with nonnegative edge weights,
  color each vertex either red or blue. Find the shortest path that
  visits all vertices exactly once (does not need to return to starting
  vertex), but does not visit vertices of the same color more than 3
  times in a row (i.e. the path

  $$red \to blue \to blue \to blue \to red$$

  is valid but

  $$red \to blue \to blue \to blue \to blue$$

  is not. Assume that there are the same number of red and blue
  vertices.

I'm trying to come up with an algorithm to at least approximate a shortest path given this constraint. My initial thought was the following (besides simply trying all $|V|!$ different paths):

Greedy Approach: Choose a starting vertex $v_0$ and at each step, simply choose the vertex $v_1$ that minimizes $d(v_0, v_1)$. However, keep a record of the colors of $v_{i}$, $v_{i-1}$, and $v_{i-2}$ at each step, and if the optimal choice of the next vertex $v_{i+1}$ violates the color constraint, choose the next best vertex.

The only problem I see with this is that you can 'run out' of vertices of a given color. That is, you could reach a point where there are more than $3$ vertices remaining, but they are all of the same color. This would make it impossible to complete the path.

My Question: Does anyone have any suggestions on algorithms to try? Maybe a modification to my suggested greedy approach to make it complete, or another paradigm all together?

(I know that this problem is $NP$-complete - that's why I'm seeking an approximation algorithm.)

Since this is your exercise, it sounds like you are only looking for a hint or an approach.  So, here is a hint/approach.

Let $M$ be a DFA (deterministic finite-state automaton) that recognizes all legal sequences of colors, where a sequence is legal if it doesn't contain the same color three times in a row.

Construct a new, bigger graph $G'$, formed by a "product construction" of $G$ and $M$.  The number of vertices in $G'$ will be at most the number of vertices of $G$ times the number of states of $M$, so $G'$ will be bigger but not too much bigger.

Now think about what you can do with this $G'$.  Try translating your original problem into some question about $G'$.


Linear-time algorithm to check monotonicity of polygonal chain A polygonal chain $C$ is called monotone with respect to a straight line $L$, if every line orthogonal to $L$ intersects $C$ at most once.

I want to design a linear-time algorithm to check whether there exists a line $L$ such that a given chain $C$ with $n$ vertices is monotone relative to $L$, and find such a line.

My idea is to take an angel of monotone chain and transfer it to the unit circle and suppose there is a line L !  like this

But I don't know how to find a good solution that the L exist

This answer is related to the remarkable answer for a similar problem. The only difference is that the OP asked about monotonicity of a polygonal chain, but not about monotonicity of a polygon.

The algorithm idea is the same - we need to determine ranges of "authorized" angles for normals to $L$ looking at the adjacent chain segments. An angle is considered authorized if a normal with this angle defines such a straight line $L$, that all the straight lines, orthogonal to $L$, intersect the chain not more than once. In case of a polygon it was enough to look at concave vertices only, but in our case we must look at all the internal vertices.

The picture below shows a polygonal chain with four segments. Authorized angles at each internal vertex are marked by green color.

If an intersection of all the $(n-1)$ ranges of authorized angles isn't empty, then the polygonal chain is monotone, and the line $L$ exists. This algorithm apparently will take $O(n)$ steps.


Binary decision diagram for a six-figure Boolean function Let $p$ be the six-figure Boolean function with the following definition:

  $p(x_{0},x_{1},x_{2},x_{3},x_{4},x_{5})=\begin{cases}
  true & \text{if } x_{0}=x_{5} \text{ and } x_{1}=x_{4} \text{ and } x_{2}=x_{3}, \\
  false & \text{else.}
\end{cases}$

  This function obviously yields $true$ iff $x_{0}x_{1}x_{2}x_{3}x_{4}x_{5}$ is a palindrome. Provide a BDD for $p$ relative to a variable ordering of your choice.

My problems begin when I try to define an appropriate variable ordering, so I am only able to guess it: $x_{0}=x_{5} < x_{1}=x_{4} < x_{2}=x_{3}$.
I'm actually pretty lost with this exercise and any help is much appreciated (sorry for not being able to provide a better own approach).

So finally this should be the correct solution:

The variable ordering is $x_{0} < x_{5} < x_{1} < x_{4} < x_{2} < x_{3}$. The BDD is:


numerical integral vs counting roots I have a problem that can be viewed in two different ways:

Compute an $n$-dimensional integral, numerical context. The domain of integration is an $n$-dimensional hyper-cube of side $L$.
Count (just count) the roots of an $n$-dimensional function (not a polynomial).

Solving just one of them is sufficient for solving the original problem.
I know that simple algorithms for numerical integration would take $O(L^n)$, taking linear time per dimension. But I am not sure if there an asymptotically faster algorithms for (1).

For (2), I am aware of algorithms that can find roots (Newton and Bisection), but I am not sure about the best algorithms just for counting how many roots are in a non-polynomial $n$-dimensional function.

What are the best algorithms for (2)? Are they better than the fastest of (1)?

Consider using Monte Carlo method for computing quadrature. It is good choice when you need not so precise approximation and dimension of the domain is large.

You definitely should provide more details.


How hard is it to solve for $P$ in $A = PBP^{-1}$? From graph isomorphism, we know that two graphs A and B are isomorphic if there is a permutation matrix P such that
$A = P \times B \times P^{-1}$

So, to solve the problem, if two graphs are isomorphic, we need to find such a permutation matrix P. The problem is believed to be NP (and NP complete for the case of subgraph isomorphism). However, I found an example to solve for P which seemed promising to me and can be found in
http://en.wikipedia.org/wiki/Permutation_matrix
in section: solving for P.

The confusion I have now is, does that work for larger matrices? very large? am I right the above equation is hard to solve and can be candidate for a cryptographic system?

Graph isomorphism has been well-studied.  A short summary: the graph isomorphism problem is not known to be in P (there are no known polynomial-time algorithms), but it is not believed to be NP-complete.  There are heuristic algorithms for  graph isomorphism that work extremely well on most instances that arise in practice.  Read the Wikipedia page on graph isomorphism for more.

As for your particular proposed approach: the Wikipedia page you linked to already explains why that method does not work in general.  That method only works if there are no repeated eigenvalues in the matrix corresponding to the adjacency graph.  Therefore, it will fail for graphs where there are repeated eigenvalues.  Such graphs cannot be ignored.  Consequently, that method may work for some graphs but it will fail (or work poorly) for other graphs, so it is not a general solution.

Graph isomorphism is not a good candidate for a basis for a cryptographic system, for two reasons.  First, existing heuristic algorithms are very good at solving the problem in practice, and it's not clear how to generate hard instances of graph isomorphism.  Second, and more seriously, to be useful for cryptography, we need to not only have a hard problem; we need to have a "hidden trapdoor" that the creator of the public key can embed, which makes the problem easy for the creator, but which is hard for anyone else to detect.  No one  knows how to embed such a "hidden trapdoor" into the graph isomorphism problem.


Unsure about parse tree of PCFG I'm new to build parse trees and I'm really unsure if I'm doing this right. So I have this example Grammar (S->Sa, S->aSa, S->a) and the word I'm parsing is simply aaaa.

My solution would look like

Is this right and is this the only possible parse tree?

Your tree is correct. However, it's not the only possible one. Your tree came from the derivation
$$
S\Rightarrow Sa\Rightarrow aSaa\Rightarrow aaaa
$$
a different one would be from
$$
S\Rightarrow aSa\Rightarrow aSaa\Rightarrow aaaa
$$


What is the time complexity of this аlgorithm? O(n * r) Given function rand7 returns random integer in interval [0, 6]. Your task is to implement function rand5 which should return random integer in interval [0, 4] using function rand7.

This is a question from my book. So, this is how I solved it (the algorithm is written in C):

int rand5(void){
  return (int)(rand7() * 4. / 6. + .5);
}

Basically, I just scaled the interval to [0, 4]. The + .5 part is to properly round to nearest integer (not just to truncate decimals). However, this is not correct solution.

Solution in my book is very weird to me. This is how they did it:

int rand5(void){
  int a;
  while((a = rand7()) > 4);
  return a;
}

The book says that the algorithm I came up with works only when interval is significantly large (so the probability will not change a lot). For smaller intervals (like this one) there is no other solution.

Well, it sounds pretty weird that there is no other solution. What is the time complexity of this algorithm? For my algorithm, time complexity is O(r) where r is time complexity of rand7. But what is the complexity of their algorithm?

The complexity should be O(r * n) where n is, according to the definition of the time complexity, the largest possible number of loop iterations. But what is the largest possible number of iterations? We know nothing about function rand7 and the way it is implemented, so the largest possible number of iterations is infinity. So, the complexity of this algorithm is O(infinity) which doesn't make any sense.

Of course, if rand7 if properly implemented, it will for sure return at lest one time number in interval [0, 4]. But, theoretically, it can return any number of consecutive numbers which belong in interval [5, 6]. Is then complexity indeterminate?

Also, how is that possible that "there is no other solution"? To generalize, is there any algorithm which can give an integer random number (with equal probability for all numbers) from interval [0, k] for given number k using only rand2 (for example), such that the algorithm should work in finite time complexity?

Edit

Ok, if I need to summarize this, the question is as title says, what is the complexity of this algorithm?

Investigating worst-case cost is rarely useful for randomized algorithms. Here, the worst case is indeed that the loop never stops -- but this event has probability zero!

Instead, perform average-case analysis. What is the probability of the loop running $k$ times?

   That means it misses the interval $k-1$ times, and then hits it. Assuming that rand7 has indeed uniform distribution, the probability of the former is $\frac{2}{7}$, and of the latter $\frac{5}{7}$. The result is, assuming that separate calls of rand7 are stochastically independent, $\bigl(\frac{2}{7}\bigr)^{k-1} \cdot \frac{5}{7}$.

Now you compute the expected number of iterations using basic facts from stochastics.

   The above weights are those of a geometric distribution. Looking up its properties, we learn that its expected value is $\frac{7}{5}$.

As it turns out, this is not too bad. You can also investigate the standard deviation or compute some probabilities to get a feeling for how unlikely high iteration counts are.


what is the 'x :=' part mean in a hoare triple? In Hoare logic, there's a thing called a Hoare triple, e.g.$$
\begin{array}{ccccc}
\{x = 2\} & & x := x+1 & & \{x = 3\}
\end{array}.
$$
What does '$x :=$' mean?

Short answer, it's an assignment, but it's not part of Hoare logic.

It means whatever it means in the programming language you're using.

A Hoare triple in general looks like $\{P\}\; C\; \{Q\}$ (stolen from the all-knowing wiki), where:

$P$ and $Q$ are assertions about the state of the system before and after $C$ is executed; and
$C$ is some piece of code.

So the meaning of $x :=$ depends entirely on the semantics of the code.

Assuming someone hasn't written this as a trick, $:=$ is usually used as an assignment operator (to avoid confusion with $=$ as equality), so in this case the line should be read as $x := x + 1$, i.e., the line of code is incrementing the variable $x$.

If the triple were written in a C-like language, you could write it as $\{x=2\}\; x=x+1;\; \{x=3\}$, or similarly in your favourite language.


Possible valid and invalid codewords I have already read different things about hamming distance, hamming code, detection and correction of memory errors, but I am still not understanding many things.

I know that the hamming distance between 2 codewords is the number of bits to be reversed to convert one codeword into the other.

I know that the hamming code is the set of all possible codewords. The codewords are composed of data bits and control bits, hence the number of bits in a codeword is n = m + r, where m is the number of data bits and r is the number of check bits. And the number of possible codewords with n bits should be $2^n$.

One thing I am not understanding is what are these valid and invalid codewords and how to 'calculate' them? Why a codeword is valid and invalid? What is the connection with the parity bits? How to find an invalid codeword?

I'm sorry if I am asking many things together, but I am really not understanding exactly the concepts I cited above.

There's no such thing as a "valid" or "invalid" codeword. If a string of bits is a codeword in a particular code such as a Hamming code, it's "valid"; if it's not a codeword, it's "invalid".


Is there any rich problems that can be solved using several algorithm techniques? I am wondering if there are some particularly rich problems that have a large intersection with algorithms and data structures. An example could be the travelling salesman problem. Any other suggestions ?

I suggest the longest increasing subsequence problem: Given an input sequence of length $n$, find the length of the longest increasing subsequence in the input sequence.
A naive dynamic programming-based formulation will lead to an $O(n^2)$ running time. The Wikipedia link provided above uses a binary search-based formulation to speed it up to $O(n \log n)$-time. Fredman '75 suggested in his paper another approach based on dynamic programming that obtains the same $O(n \log n)$ time bound, and established a lower bound in terms of the number of comparisons, proving his algorithm is the best possible.
But this is not the end of story, yet. There are various other algorithms that solve LIS. Using advanced data structures, Crochemore and Porat gives a priority queue-based algorithm for solving LIS in $O(n \log \log k)$-time on a word RAM. Yet other techniques exist, such as reduction to range maximum queries and then solving the problem via tournament trees 1, and using van Emde Boas trees. Finally, there is also a divide and conquer-based algorithm that solves LIS by Alam and Rahman, running in the same $O(n \log n)$ time bound.
The LIS problem also has connections in mathematics, it is related to a combinatorial structure called the Young tableaux (https://en.wikipedia.org/wiki/Young_tableau; in particular; the maintenance of the principle row of the Young tableaux is essentially solving for longest increasing subsequence) and the Robertson-Schensted correspondence.
Plenty of other problems in string pattern matching also have produced a rich body of results; I'm sure you'll find an abundance of other problems that are close in richness to longest increasing subsequence.


Smart most recently used algorithm Background
I need such an algorithm inside an android app (home launcher) to show the recently used apps. I want to avoid simple LRU / MRU logic by combining those logics (or use an alternative if anyone has a suggestion). I don't want an app that was started 100x before 10 weeks to stay on top until another app was started 100x and I don't want to only show the LRU apps on top. I want something that matches what a human would expect to see in the most recently used section.
Solution
I can of course save every app launch in a database (including its timestamp) and then give each launch a weight based on its age and then sum them up and calc an avarage value. That's a valid solution and would fit my needs. BUT it will grow the database indefinitely.
Question
Does anyone has an idea or does there exist an algorithm for such a problem already that does not depend on a full list of historical data (app launches in my case)? But instead does update values that belong to each app?

I suggested looking at the Reddit ranking system in a comment, however,
that system is made in such a way that the time of creation is what
matters, and that's not really relevant in your scenario.
I therefore suggest a physics-based approach.
Model each app as a balloon (circular, in vacuum).  Every time you open
an app, it corresponds to hitting the balloon straight upwards (like a
volleyball set hit), and when you're not hitting the balloon, it falls
towards the earth.  Once it hits the ground it can remain idle (or bump
up a bit if you want to remind the user of apps they forgot about).
In order for an app to remain "hot" you need to keep it above ground.
So how to implement this?
We have a list of timestamps that maps days since epoch to the number of
times it was opened that day.  In the below sketch, I use a linear decay
(gravity would of course be quadratic).
You need to experiment with the constants and try different functions
(logarithms and polynomials) to get it to work to your likings.
Sketch
USAGE = {  # map day to number of opens for that day
    "A": {0: 2, 1: 2, 2: 2, 3: 2, 4: 2},
    "B": {0: 10, 1: 0, 2: 0, 4: 0},
    "C": {0: 0, 1: 3, 2: 3, 4: 3},
    "D": {0: 0, 1: 0, 2: 0, 3: 5},
    "X": {0: 3, 1: 3, 2: 3, 3: 3, 4: 0},
    "Y": {0: 0, 1: 0, 2: 0, 3: 0, 4: 3},
    "Z": {0: 0, 1: 0, 2: 0, 3: 0, 4: 2},
}
IMPACT = 1.1
DECAY  = 1.1

def rank_app(timemap, t):
    """Return the "height" of the balloon on day t given the timemap"""
    height = 0
    for day in range(t + 1):
        height += timemap.get(day, 0) ** IMPACT  # impact of opening
        since = abs((t - day - 1))
        height = max(0, height - since ** DECAY)  # decay
    return round(height, 1)

def rank(usage, day):
    """Return (heigh, app) for each app on given day t."""
    return sorted(
        [(rank_app(usage[app], day), app) for app in usage],
        reverse=True,
    )

print("\n".join([f"{e[0]} {e[1]}" for e in rank(USAGE, day=5)]))

... which gives
3.9 D
2.6 X
2.6 C
2.3 Y
2.3 A
1.1 Z
0.5 B

Notice that D is on top because it was visited 5 times yesterday.  On
the other hand, B was visited 10 times on Day 0, but hasn't been
visited since, so it is on the bottom.
If you are worried about the space it takes to store all the timestamps,
you can truncate the list at any point and replace with its height at a
given day.


Does having one large L1 cache instead of L1 and L2 cache makes computation faster? Does having one larger L1 cache instead of L1 and L2 cache makes computation faster? Also will this make the CPU more expensive to make?

Whether a shallower memory hierarchy provides better performance depends on the workload, the microarchitecture, and the implementation technology.

A workload that has a high miss rate for a "conventionally-sized" L1, when run on such a processor, would have more overhead in transferring cache blocks from L2 to L1 and (if writeback) dirty blocks from L1 to L2. In addition, if access to L2 was only started when a miss in L1 is determined, then latency for L2 would be larger (even if L1 in the shallow hierarchy processor used the same memory array implementation as L2).

A microarchitecture suited to modest-sized L1 caches would be biased (relative to one suited to huge L1 caches) toward speed-demon rather than brainiac design, exploiting the lower latency of a cache hit. (Workload, implementation technology, and other factors influence other tradeoffs with respect to speed-demon vs. brainiac.)

If the targeted workload can benefit from extensive hardware threading, providing a larger (and more associative) L1 can be advantageous as the thread-level parallelism can hide greater L1 access latency.

If the implementation technology reduces the latency penalty of a larger cache, the variety of workloads where the tradeoffs (in miss handling overheads and other factors) weigh in favor of a shallower memory hierarchy will increase. For example, in the future it is conceivable that 3D integration might be used for L1 cache and the memory used for this might have relatively high cell access latency (for low power to avoid thermal issues associated with 3D integration), so reduced distance (from 3D integration) and slower memory cells could increase the incentive for a larger L1 cache.

These types of questions become even more complex when one considers that the definition of L1 cache can get somewhat less clear. For example, if what would conventionally be called L2 cache is accessed in parallel with L1 but with higher latency, is it an L2 cache or part of a non-uniform cache architecture L1, especially if some cache blocks are never allocated to the smaller portion of the cache (cache bypassing has been proposed as a mechanism to better utilize capacity and bandwidth). (Even the NUCA L2 cache proposals allowed for transfers between slow and fast portions of L2.) Way prediction can also introduce variable latency for L1; if the prediction mechanism included consideration of expected criticality (and such was used for allocation to near or distant memory arrays within a NUCA design), one might reasonably consider the far memory arrays part of the L1 cache even though their inherent access latency is greater.

(Itanium 2 did not even probe the small L1 data cache for floating-point register loads, so for floating-point data one could almost consider the L2 cache as an L1 cache.)


Using induction to prove transition states are the same Suppose that you have a DFA $M=\left(S,\Sigma,s_0,\delta,{s_f}\right)$ with $s_f\neq s_0$.

Suppose further that, for all $a\in\Sigma$, $\delta\left(s_0,a\right)=\delta\left(s_f,a\right)$.

Show that for any non-empty word $w$ over $\Sigma$, we have $\delta^{*}\left(s_0,w\right)=\delta^{*}\left(s_f,w\right)$.

I know there is something I am overlooking, specifically with regards to the non-empty word. Here is my attempt at an answer via a proof by induction:

Let's use a word $w=ax$

$$\delta^{*}\left(s_f,ax\right)=\delta\left(\delta^{*}\left(s_f,a\right),x\right)$$

Since $\delta^{*}\left(s_0,w\right)=\delta^{*}\left(s_f,w\right)$.

We can also write this equation as
$$\delta^{*}\left(s_f,ax\right)=\delta\left(\delta^{*}\left(s_f,a\right),x\right) = \delta\left(\delta^{*}\left(s_0,a\right),x\right)=\delta^{*}\left(s_0,ax\right)\,.$$

This seems almost too obvious... I am new to this style of maths and would appreciate some guidance with regards to my proof style and if I'm ommitting something significant.

New attempt thanks to @Patrick87's guidance:

$$\delta^{*}\left(s_f,ax\right)=\delta^{*}\left(\delta\left(s_f,a\right),x\right) = \delta^{*}\left(\delta\left(s_0,a\right),x\right)=\delta^{*}\left(s_0,ax\right)\,.$$

I think this makes sense but I can't help but feel something is missing.

We use induction on the length of $w$. Let this length be denoted by $|w|$

Base case: $|w|$ = 1

Immediate by the assumption that $\forall a∈Σ. δ(s_0,a)=δ(s_f,a)$

Induction hypothesis: $δ^*(s_0,w)=δ^*(s_f,w)$ for $|w| = k$ where $k \geq 1$

Inductive step: Assuming the induction hypothesis, prove that it works for $k+1$:

Let $w$ be a word s.t $|w| = k+1$. Clearly $w$ can be seen as two strings $w = w^{-1} \circ v$ where $\circ$ is concatenation of strings.

As $|w^{-1}| = k$ we, by induction, get that $δ^*(s_0,w^{-1})=δ^*(s_f,w^{-1})$. As $x$ is a string of length $1$ we get by $\forall a∈Σ. δ(s_0,a)=δ(s_f,a)$ that $δ^*(s_0,w)=δ^*(s_f,w)$

The proof could be a bit more formal, but atleast the intuition should be clear.


Factoring algorithms after number field sieves It seems that the General Number Field Sieve (GNFS) became number one and then RSA stopped its factoring challenges and there have been no advances in factoring algorithms besides quantum computers. So are there faster algorithms after GNFS for classical computers? Note that the 1980s and 1990s saw a series of new factoring algorithms, including elliptic curve and quadratic sieve. And then progress stopped.

From the first line of Wikipedia's GNFS page:

"the general number field sieve (GNFS) is the most efficient classical
algorithm known for factoring integers larger than"

The following factorizations of RSA numbers used none other than the GNFS algorithm:

February 2020: RSA-250
December 2019: RSA-240
February 2020: RSA-232
August 2018: RSA-230
May 2016: RSA-220

Conclusion: The top researchers in the field are breaking factorization records using none other than GNFS (usually the CADO-NFS implementation). If there was a faster factorization algorithm for arbitrary semi-primes, surely the groups of Zimmerman and Lenstra would be using it, or at least mentioning it somewhere in their papers. GNFS is still the fastest for arbitrary semi-primes. For specific semi-primes like $p^2$ where $p$ is prime, there's faster algorithms such as doing the square root.
A more interesting question might be: What are some recent developments in the field of factoring numbers on classical computers? I might also be interested if there's anything promising out there that's been developed recently and might have a chance at beating GNFS one day. Also if you look at the above references, the authors will tell you of great achievements in improving implementations of the GNFS algorithm (for example the matrix step used to be harder than the sieving itself, but that was sorted out at around the time of factoring RSA-220).


What algorithm to use for this subset sum problem I have a typical subset sum problem and I'm looking to choose the proper algorithm to solve it, the set contains (around) 1000 elements, and elements are constrained to max 22 bits for now.

I have been looking around and looks like the well known O(2^(n/2)) is not an option, and looking into the Dynamic Programming version memory becomes a big concern, because the elements values are pretty balanced

n=1000
s=962,425,151 (Avg=964,452)

Array required: [1000,964452152] =    964,452,152,000 bytes

Even using a bit array, (given I'm estimating the algorithm requirements properly), it will require 112 GB of memory... (964,452,152,000/8 =     120,556,519,000 bytes)

Is there other known subset sum algorithm I could evaluate?

Edit 1: (after Tom reply)

I didn't clarify this in the question:

It must be an exact algorithm (not approximate solutions)
Should be able to output the subset solving s

You can implement the dynamic programming algorithm using a much smaller amount of memory. You don't need the entire table in memory all the time.

The point is that to answer the question "Is there a set of items $1,\ldots,i$ that sums to $s$?", you only need the answers for $i-1$ (the previous "row" in the DP table), but you don't care about the (previously computed) answers for $i-2,i-3,\ldots$. Thus, at any given time, you'd only need an two arrays of around 120MB each in memory (and in fact, you can do it using only one array!).

However, reconstructing the solution becomes more difficult, since traditionally you'd reconstruct the solution by backtracking through all of the stored values. There's a nice workaround: with each (feasible) subproblem, store how much of the weight is taken up by the first $n/2$ elements.

We can do this computation in time $O(ns)$ (where $s$ is the sum of all elements). From the final row of the dynamic programming table, we can now find not only whether the problem has a solution at all, but also (if a solution exists), what portion of the target sum is achieved by the first $n/2$ elements (and consequently, we also know what portion of the sum the remaining elements make up). We can now solve the two subproblems recursively, each of half size. The total time taken is only $O(ns \log n)$, i.e., we only take a factor $O(\log n)$ hit in the running time for a linear reduction in memory usage.

You should also consider the possibility that perhaps not all possible values can be attained as sum of items in your set. So, depending on the input, perhaps not using a contiguous array of bits, but using instead for example a hash table will use less memory.

Finally (as an alternative solution), if you only need an approximation, consider rounding the values (e.g. to the nearest thousand) to reduce the size of the tables further.


Solving a bivariate recurrence equation I'm dealing with this recurrence equation:

$\qquad\displaystyle T(m, n) = T(m/2, n/2) + T(m, n/2) + O(1)$.

Any idea how to solve this? I've looked in to few advanced resources but the literature on two dimensional recurrence equation seems to be very thin.

Repeated substitution

Repeatedly substitute in, and look for a pattern:

$$\begin{align*}
T(m,n) &= T(m/2,n/2) + T(m, n/2) + 1\\
&= T(m/4,n/4) + 2 T(m/2,n/4) + T(m, n/4) + 3\\
&= T(m/8,n/8) + 3 T(m/4,n/8) + 3 T(m/2,n/8) + T(m, n/8) + 7\\
&\vdots\\
\end{align*}$$

Do you see the pattern?  The coefficients $1,3,3,1$ should remind you of binomial coefficients.  The pattern is

$$T(m,n) = 2^k-1 + \sum_{i=0}^k {k \choose i} T(m/2^i, n/2^k).$$

You can prove that this holds for all $k$ (by induction on $k$).  Then, setting $k=\lg n$, we find

$$T(m,n) = n-1 + \sum_{i=0}^{\lg n} {\lg n \choose i} T(m/2^i, 1).$$

So it suffices to know how to evaluate $T(m,1)$ for all $m$.  That information cannot be deduced from the recurrence you gave us -- it needs to be supplied as additional base cases.

For instance, suppose we are given the base cases $T(m,1) = 1$ for all $m$.  Then we find

$$T(m,n) = n-1 + \sum_{i=0}^{\lg n} {\lg n \choose i} = 2n-1 = \Theta(n).$$

However, if we were given different base cases, the solution might be different.

Guess-and-check

Another approach is to somehow guess the solution (for instance, by playing with a bunch of examples and looking for patterns), and then check that it holds.  For your example, if we assume $T(m,n) = T(m/2,n/2) + T(m,n/2) + 1$ and we assume $T(m,1)=1$ for all $m$, then rubbing our rabbit's foot for luck, we might get lucky and guess

$$T(m,n) = 2n-1.$$

It is then easy to plug in and confirm that this is a valid solution to the recurrence you gave.

However, in general, guess-and-check is often very hard -- you can try many guesses, but sometimes it can be very difficult to find a guess that turns out to be correct.


What are the benefits of languages that are not Turing complete? Unfortunately I did a degree in CS without much theoretical computer science. One thing I used to hear is that sub languages, or languages which are not Turing complete, allow for better optimization?

Why is this case? What is the thought process and what are some examples in practice? What are some good resources on the topic?

The main advantage of having a Programming Language that is not Turing Complete is that your language can be strongly normalizing, that is, you can ensure that all terms halt with a unique, well formed value.

I've come across non-Turing complete languages primarily with proof assistants. When you're using programs to prove theorems, you need to make sure that all terms halt, since otherwise you can produce non-terminating terms of type False. This also ensures that type checking is decidable with dependent types, since we need to evaluate code with type checking. Agda and Coq are both languages that are not Turing Complete. This also ensures that you can't accidentally write an infinite loop, which is the motivation behind things like the Dhall language.

As for what you mention about program analysis, Rice's theorem means that any analysis of a Turing Complete language is either unsound or incomplete. So if you use restricted languages, you might be able to write analyses that are precise.


Why proving programs correctness doesn't have the same importance as algorithms analysis or the theory of computation in practice? What are the major causes that makes "Proving Programs correct", not a widely attractive subject? though from it's name, and from what we know from other disciplines (like mathematics) it looks like it should be on the top of the "must know list". And by the way I'm talking about "the real world", in practice.

On the contrary, it's certainly important practice, and is a huge area of research!

Perhaps a better question might be, "why is proving programs correct not common in practice, or not a main feature of an undergraduate curriculum?"

There's a few reasons for this:

Proving programs correct is hard. The proofs often end up being long and tedious proof-by-cases, and will usually have less interesting intellectual content that you'd see in most math proofs.
You need a formal semantics for whatever language your program is specified in. For real world programming languages, developing such a semantics is often difficult, since there are possibly corner cases or odd compiler behaviors that are difficult to model
Proving a program correct only proves that it matches a given specification. What if there's a bug in the specification?
Proving a program correct assumes that it's being compiled by a correct compiler, or run by a correct interpreter, which almost never the case.

Things also change by what you mean by a "program". For example, in real world algorithms research, almost every time someone publishes a new algorithm, they will provide a proof of correctness. Usually this is working on pseudocode with a simple but straightforward semantics, so lots of the formal details from above aren't an issue.

Also, just to counter your claim that it's not an area of research:

The entire field of Dependent Types is focused on proving real, running programs correct using type theory. There are lots of great projects in this area, like DeepSpec.
Formal methods is an entire field devoted to proving program correct, usually adapting methods from hardware verification to software.


Algorithm for estimating function maximizing parameters I'm trying to find parameters $\omega, \alpha,$ and $\beta$ which maximize

$$
\sum_{i=1}^m{\left\{ -\ln(v_i) - \frac{r_i^2}{v_i} \right\}}
$$

where

$$
v_i = \omega + \alpha r_{i-1}^2 + \beta v_{i-1}^2
$$

Since numerical values for $r_i$ and $v_1$ are given my first thoughts were to use the normal equation

$$
\Theta = (X^TX)^{-1}X^Ty
$$

This I realized quickly wouldn't work because there are no observed values of $v$ to fill $y$ with. I similarly considered something along the lines of gradient descent but then again I ran into the same problem. I only have $v_1$ as a starting point but no observed $v_2, v_3$ etc. I've also found my way on the Levenberg-Marquardat wikipedia page but then again I came up empty because I can't figure out how to produce (independent, dependent) bundles under these conditions.

The problem I'm basically trying to solve is that of estimating the three parameters of a GARCH(1,1) model ($v_i$ above).

MathLab offers tools which can estimate these parameters for me but what I'm trying to do is understand how the under-the-hood algorithm works in coming up with these numbers. Even excel's solver can figure out these parameters given an initial guess but I have not been able to find how it actually works. I understand that starting from an initial guess it uses an iterative method to arrive at a solution but I can't figure out how it updates the parameters at every run.

You have a function $f:\mathbb{R}^3 \to \mathbb{R}$, which accepts three real numbers as input and produces a real number as output.  You want to find values $\omega, \alpha, \beta$ that maximize $f(\omega, \alpha, \beta)$.

This is a standard problem in mathematical optimization, and there are a variety of techniques for solving this problem.

Black-box methods. The methods that are easiest to use treat $f$ as a complete black box: all we need is  a way to evaluate $f$ at any input of our choice.  Example methods include hill climbing, coordinate descent, (well, in this case it will be coordinate ascent, since you want to maximize $f$), gradient descent (well, in this case it will be gradient ascent, since you want to maximize $f$), Newton's method, conjugate gradient methods, and more.
Black-box, plus derivatives. Some of these methods can be sped up significantly if we have an efficient way to evaluate each of the partial derivatives of $f$ at any input of our choice.  Sometimes, if $f$ has a simple representation, we can compute the partial derivatives of $f$ algebraically, which then gives us a way to evaluate these functions at any desired input.  The reason this speed things up is that some of the black-box methods effectively end up approximating the partial derivatives or 2nd partial derivatives (e.g., the gradient or Hessian matrix) as part of the process; if you have a faster way to compute them directly, then those methods become more efficient and more effective.
Dedicated methods. There are other methods available if the function $f$ has a particular algebraic form, e.g., linear programming, convex optimization, and more.  These probably won't apply to you, so they can be safely ignored in your situation.

Many tools, like MathLib, include built-in libraries to apply these methods for you.

In your case, the function $f$ is given by $f(\omega, \alpha, \beta) = \sum_{i=1}^m{\left\{ -\ln(v_i) - \frac{r_i^2}{v_i} \right\}}$ where $v_i = \omega + \alpha r_{i-1}^2 + \beta v_{i-1}^2$.  But those details aren't important; what's important is that, given $\omega, \alpha, \beta$, you can evaluate $f$ to learn the value of $f(\omega, \alpha, \beta)$.  That allows you to apply black-box optimization methods.

One generic issue to be aware of is that many of these methods may only produce a local optimum, not a global optimum.  There are a variety of heuristics for dealing with this, but generally none that are guaranteed to work in all cases.  Often, the methods are fairly sensitive to the choice of starting point, so if you have a good guess at a value of $\omega, \alpha, \beta$ that is likely to be near the optimal value, then starting the methods from there can be helpful.  Also, it can be helpful to apply the methods multiple times, from different (random) starting points and take the best observed over all iterations.


On different characterizations of $\mathsf P$ In here it was clarified that $\cap_{f(n)\in\omega(1)}\mathcal C(n^{f(n)})\subsetneq\cap_{\epsilon>0}\mathcal C(n^{n^\epsilon})$ where $\mathcal C(t(n))$ is the class of problems solvable in $O(t(n))$ time.

My query now is whether there is a function of $g(n,\epsilon)$ that non-trivially depends on $\epsilon$ with $g(n,\epsilon)<g(n',\epsilon')\implies\epsilon<\epsilon'\vee n<n'$ such that
 $\cap_{f(n)\in\omega(1)}\mathcal C(n^{f(n)})=\cap_{\substack{\epsilon>0}}\mathcal C(n^{g(n,\epsilon)})$ can hold?

That is I seek a different characterization of $\mathsf{P}$.

I will consider the following simpler version of your question: is there a function $g(n,\epsilon)$ such that the following are equivalent, for a function $f(n)$:

$f$ is bounded.
For every $\epsilon > 0$ there exists $N$ such that for $n \geq N$, $f(n) \leq g(n,\epsilon)$.

Consider first the case in which $g(n,\epsilon_1)$ eventually exceeds $g(n,\epsilon_2)$ whenever $\epsilon_1 > \epsilon_2$ (like your example $g(n,\epsilon) = n^\epsilon$). Then the second condition can be rewritten equivalently as

For every integer $M$ there exists $N$ such that for $n \geq N$, $f(n) \leq g(n,1/M)$.

Define the function
$$ f(n) = \max_{M \leq n} g(n,1/M). $$

This function satisfies condition (3), and so is bounded, say $f \leq C$. This implies $g(n,1) \leq C$. But then the bounded function $C+1$ doesn't satisfy condition (3) for $M=1$. This contradiction shows that under the stated constraint, no function $g$ fits the bill.

On the other hand, as you mention, $f$ is bounded iff it is eventually dominated by every $\omega(1)$ integer function. Indeed, suppose that $f$ is unbounded. Then for every integer $M$ there exist infinitely many $n$ such that $f(n) \geq M$. In particular, we can find an increasing sequence $n_1,n_2,\ldots$ such that $f(n_M) \geq M$. Define a function $g$ by $g(n) = M-1$ for $n_{M-1} < n \leq n_M$. Then $g = \omega(1)$ but $f$ is not eventually dominated by $g$.

The functions from $\mathbb{N}$ to $\mathbb{N}$ have the cardinality of the continuum, and so they can be put (constructively!) in one-to-one correspondence with the real interval $(0,\infty)$. This immediately gives a function $g(n,\epsilon)$ which does fit your bill, though is not particularly natural.


Proving that for every computable function f: N → N, there exists a computable function g: N → N such that for every n we have f(n) ≤ g(n) Prove that for every computable function $f \colon \mathbb N \to \mathbb N$, there exists a computable function $g \colon \mathbb N \to \mathbb N$ such that for every $n$ we have $f(n) ≤ g(n)$.

Can anyone please explain me, why my proof below is not correct?

  Lets assume, for the sake of arriving at a contradiction, that there exists a computable function $f$ such that for every computable function $g$, there
  exists an $n$ such that $f(n) > g(n)$.

  For each computable function $g$, let $n(g)$ be the smallest $n$ such that $f(n) > g(n)$. Let $n_0$ be the maximum of $n(g)$ over all computable
  functions $g$, and assume that this maximum is achieved for $g_0$, that is,
  $n(g_0) = n_0$.

  Define a function $g_1$ that is equal to $g_0$ for all values except for $n_0$, and for $n_0$ we have $g_1(n_0) = f(n_0)$. This function $g_1$ is computable because $g_0$ is computable and $g_1$ differs from $g_0$ in only one point. By definition, $n(g_1) ≥ n(g_0) + 1$, and this contradicts the fact that $n(g)$ was maximized at $g_0$.

The problem with your proof is in the definition of $n_0$. The function $n(g)$ can be unbounded (as a function of $g$).

A much simpler proof would be to take $g = f$.


How to partition a set into disjoints subsets each of given size? The input: Given a set $U=\{1, \ldots, k\}$ called the universe. Let $C=\{S_1, \ldots, S_n\}$ be a collection of subsets of $U$ and let $ s_j$ be a nonnegative integer for all $j=1,\ldots,n$ such that $\sum_{j=1}^{n} s_j=k$.

The question: Are there $n$ subsets $A_j$ of $S_j$ (i.e., $A_j\subset S_j$) such that

$$
\quad\bigcup\limits_{j=1}^{n}A_j=U,\\
\quad \quad\;\;\;\,\;\;\,A_j \cap A_i = \emptyset, i\neq j,\\
|A_j|=s_j.
$$

Is this problem NP-hard?

I was trying to reduce PARTITION to this problem by setting $n=2$ and $k$ an even number and $s_j=k/2$ but the constraints $|A_j|=k/2$ do not help me.

When $s_j = 1$ for all $j$, the problem is the same as deciding whether a bipartite graph has a perfect matching. In the general case, we can solve it using maximum flow.

Set up a flow network with the following components:

A source $s$, a sink $t$, a vertex $S_j$ for each set, and a vertex $x_i$ for each element in the universe.
Connect $s$ to each $S_j$ with an edge of capacity $s_j$.
For each $x_i \in S_j$, connect $S_j$ to $x_i$ with an infinite capacity edge.
Connect each $x_i$ to $t$ with an edge of capacity $1$.

Now compute the maximum flow. If it equals $|U|$ then the instance has a solution. Moreover, you can extract the solution from a maximum integer flow.

The max flow min cut theorem also gives us a Hall-like criterion: a solution exists if for every set $X$ of elements,
$$ \sum_{j\colon S_j \cap X \neq \emptyset} s_j \geq |X|. $$
That is, if we sum the "capacities" $s_j$ for all sets $S_j$ that intersect $X$, then we need to get at least $|X|$. This is clearly a necessary condition, and the max flow min cut theorem shows that it is sufficient.


Binary Search Tree Traversal output validity and unique BST construction I had two specific type of questions involving Binary Search Tree (not simple Binary Tree) traversals :

Given x-order traversal output of BST, can we state if it is valid or invalid output?
(For example, this: [3,2,1,4,6,7,8,5] can be valid postorder traversal output, but this: [4,1,3,2,6,7,8,5] cannot be.)

Given x-order traversal output of BST, can we draw unique BST?

Put Pre, Post, In and Level in x. So there are actually 8 questions.
I didnt find any place discussing these all. But after a bit of thinking I realized that,

for all x-order traversal outputs, we can state whether it is valid or not.
for all x-order traversal outputs except the inorder, we can draw unique BST.

This is really confusing me. Especially in case of inorder. Logically, it seems that if we can construct unique BST for given x-order traversal output, then we can say that for that x-order traversal output, we should be able to tell whether the output is valid or not. But this does not seems to be correct, since in case of inorder traversal, we can tell if the given output is valid or not but we cannot construct the corresponding unique BST.

I believe you are correct. The hard part is convincing yourself why this is true, I guess.

The key to the riddle is the root. preorder, postorder and levelorder all have the root at first or last position. Once the root is known all elements smaller go in the left subtree and those larger go right. Thus reconstructing the tree from its order is a recursive process.

Inorder always yields the elements from small to large, so there the situation is completely different. There is no unique tree, and any tree that is built by adding the elements as a BST will do.


What is a good path for self-study of CS foundations/fundamentals? I’m a self-taught software engineer who’s been working in industry for 12 years. I don’t have any formal education in CS and math was never my strong suit (although I’m willing to do the work to make it my strong suit!), but when I first started learning how to program I went through some basic courses offered by Stanford, MIT, etc.
Anyhow, I’m looking to gain a more rigorous understanding of CS, starting from the most basic, foundational pieces. I’m looking for some guidance on a good course of self-study - the order to go in, suggested resources, etc.
Given that I’m looking to understand CS fundamentals more rigorously, as I said, I’m beginning with some basic math (not my strong suit). What I’ve mapped out so far is going through the following books (and investigating prerequisites/dependent concepts for these materials on an as-needed basis):

Discrete Mathematics with Applications 4th edition by Susanna Epp
Practical Analysis of Algorithms by Dana Vrajitoru, William Knight
Book of Proof Richard Hammack
Mathematics for Computer Science by Lehman, Leighton, Meyer

I have a bit of a tendency to get down the rabbit hole and go on detours, whereby the main purpose of my study recedes into the distance as I investigate yet another area that I don’t seem to have a solid foundation in. But I’m unsure how to avoid this as some things really do need to be understood before other things. For example, without understanding some basic discrete maths, it will be difficult to talk about recursion, time complexity in a way that is more rigorous than my current understanding.
Perhaps I’d be better suited just starting immediately with MIT’s “Mathematics for Computer Science” course (6.042J) and only looking into things I don’t have a grasp on as needed?
Anyhow, sorry for the ramble. Would love some general guidance and direction for getting to where I’m trying to go. Thanks in advance.

Check out this and this. I prefer the former one cause the number of subjects is relatively small, and they are the core fundamentals.


Is it possible fo find a vertex-cover of size $\lceil \log |V| \rceil$ in polynomial time? If we have a graph $G=(V,E)$, can we find a vertex cover with size $\lceil \log |V| \rceil$ in polynomial time?

Let the input graph be $G=(V,E)$ and let $k$ be the (maximum) size of the vertex cover of $G$ we are searching for. Proceed as follows:

If $E=\emptyset$ return the trivial empty solution.
Otherwise, if $k>0$:

Pick an arbitrary edge $(u,v) \in E$.
Recursively search for a vertex cover $S$ of size (at most) $k-1$ on the graph $G - u$. If $S$ exists return $S \cup \{u \}$.
Recursively search for a vertex cover $S$ of size (at most) $k-1$ on the graph $G-v$. If $S$ exists return $S \cup \{v \}$.

Return "no solution exists".

The time complexity of the above algorithm can be described by the following recurrence relation, where $n$ is the number of vertices of the input graph for your problem.
$$
T(k) \le 2T(k-1) + O(\mbox{poly}\, n) \quad \mbox{and} \quad T(0)=O(1).
$$
Therefore $T(k) = O( 2^k \cdot  \mbox{poly}\, n )$.
In your case $k=\lceil \log n \rceil$, therefore the overall time needed is $O( \mbox{poly}\, n )$.


Can the heaviest edge ever be in an MST? Is it true that the heaviest edge in a directed graph can not be in the MST of that graph?

I don't think it is true because we might end up with a heaviest edge that is not part of a cycle.

Can anyone confirm?

No, it is not true. Consider a graph with 2 vertices and an edge between them. This is the heaviest edge, and it will be in the minimum spanning tree of $G$.


Algorithm for a special case of SAT/#SAT Does anyone know of an algorithm that can solve the following special case of SAT in polynomial time? Are there any algorithms that can solve the counting (#SAT) version of it in polynomial time?

Special case:
If clause $a$ and clause $b$ have one or more variables in common, that is, there exists some variable $x$ that is in both $a$ and $b$, at least one of the shared variables is positive in $a$ and negated in $b$ or vice-versa.

Example:
$$(a \vee b \vee c) \wedge (\bar{a} \vee c \vee d)$$

Example of an instance that does not fit in the special case:
$$(a \vee b \vee c) \wedge (a \vee c \vee d)$$

From Solving #SAT using vertex covers, published at SAT'06 by Naomi Nishimura, Prabhakar Ragde, and Stefan Szeider:

  A cluster formula is a variable-disjoint union of so-called hitting formulas; any two
  clauses of a hitting formula clash in at least one literal. The known polynomial time
  algorithm for computing the number of models of a hitting formula can be extended in a straight-forward way to compute the number of models of a cluster formula.

Clash is later clarified/defined as:

  We consider propositional formulas in conjunctive normal form (CNF), represented
  as sets of clauses. That is, a literal is a (propositional) variable $x$
  or a negated variable $\overline{x}$; a clause is a finite set of literals not containing a complementary pair $x$ and $\overline{x}$; a formula is a finite set of clauses. For a literal $ℓ = \overline{x}$ we write $\overline{ℓ} = x$; for a clause $C$ we set $\overline{C} = \{ \overline{ℓ} : ℓ ∈ C \}$. We say that two clauses $C$, $D$ overlap if $C ∩ D \neq ∅$; we say that $C$ and $D$ clash if $C$ and $\overline{D}$ overlap. Note that two clauses can clash and overlap at the same time. [...] A formula is a hitting formula if any two of its clauses clash (see [17]). A cluster
  formula is the variable-disjoint union of hitting formulas [...]

  Lemma 3. #SAT can be solved in polynomial time for cluster formulas.

So their cluster formula seems to be exactly what you have defined.

There's also a journal version that paper, it seems; the result is (not surprisingly) also mentioned in a 2011/2012 survey paper "Backdoors to satisfaction" on which Szeider is a co-author, and which was published in some festschrift My first instinct that this was a more suitable question on cstheory.SE was perhaps not wrong. :-)

Also the notion of hitting formulas is cited to [17]:

H. Kleine Buning and X. Zhao. Satisfiable formulas closed under replacement.
In H. Kautz and B. Selman, editors, Proceedings for the Workshop on Theory
and Applications of Satisfiability, volume 9 of Electronic Notes in Discrete
Mathematics. Elsevier Science Publishers, North-Holland, 2001.

In another paper, the fact that

  It is known that for hitting formulas the satisfiability problem can be solved efficiently [7].

is cited to an even older paper:

K. Iwama "CNF satisfiability test by counting and polynomial average time" SIAM J. Comput., 18 (1989), pp. 385–391


For what values of A and B is the gap-VC-[A,B] problem NP-HARD? For which values $A,B$ is the problem $\mathsf{gap\mathord-VC}\mathord-[A,B]$ NP-hard? VC is the vertex cover problem. I am given three options: $B=\frac{3}{4},A=\frac{1}{2}$ or  $B=\frac{3}{4},A=\frac{1}{4}$ or none.

I would to review what I think that I need to do, I'm not sure that the way I think of it is correct. This is what I think: I need to decide if it NP-hard to approximate the VC to $\frac{1}{2}$, i.e., can I build an NP Turing machine that would return Yes iff for a given graph, it can guarantee that it has less than $\frac{1}{4}V$ vertices that cover the whole graph? Maybe even for $\frac{1}{2}V$ vertices?

 This is a question from a past midterm that I'm solving now in order to prepare myself for my own midterm in a "Computational Complexity Theory" course.

Vertex cover has an easy $2$-approximation, so gap-VC-[$1/4,3/4$] is easy. The best unconditional hardness result is by Dinur and Safra, which gives $1.3606$ hardness. Since $(3/4)/(1/2) = 1.5 > 1.3606$, their method definitely doesn't imply gap-VC-[$1/2,3/4$]-hardness. Assuming the Unique Games Conjecture, the hardness of vertex cover is $2-\epsilon$, but this doesn't necessarily imply that gap-VC-[$1/2,3/4$] is hard - you'd have to look at the proof to determine that.

In summary, I have no idea what the correct answer is, and I'm not sure that anyone else knows which answer is correct (unconditionally).


Which type of control unit used in modern processor? Is it hard wired CU or microprogramed?

x86 are famous for using microcode, because there are a few complex operations, such as call gates or how the x87 calculates sines or exponentials, which cannot be reasonably constructed with a simple finite state machine. x86 also have very extensive patching resources, which allows to fix some bugs on released silicon, and which is probably handled through microcode (Some hints are probably in the patents from Intel and AMD).

Small ARM CPUs don't need and don't use microcode. The "R" and "M" classes.

High end ARMs such as Apple's... Who knows ? Besides the visible instruction set, there are also many hidden stuff, for example for debugging, self-testing the hardware and for power management, which may be based on microprograms.

The general trend nowadays, is that, even in x86, the instructions that need performance are decoded directly which is faster and more power efficient that fetching microcode memory.


How does the cpu know which process to wake? In general, my understanding is: the cpu is executing a process/thread until either it is interrupted, the scheduler kicks it out, or it's waiting for something else (I/O for example), when it's put in different queues (ready, waiting, etc). (Correct me if I'm wrong)

My question is, when one process is waiting information from another process (I guess, sleeping until a signal for it has been received). How does the cpu know how to wake that process? When it receives the signal will it be attempting to wake up all the processes with it? Is it marked somehow which processes are expecting which signals? What if the interrupt doesn't have this process id, but a general message to which the process is the only one waiting for it?

I've been trying to find a concrete response and read:
https://learning.oreilly.com/library/view/operating-system-concepts/9781118063330/10_chapter03.html#chap3
https://medium.com/cracking-the-data-science-interview/how-operating-systems-work-10-concepts-you-should-know-as-a-developer-8d63bb38331f

Thanks in advance!

TL;DR
The CPU doesn't know anything. The operating system (OS) knows it all.

The CPU is rather a stupid machine that activates one instruction at a time, without knowing what that instruction "means" nor to which program it "belongs". To the CPU eyes there is only a single program that runs (maybe, up to interrupts that "jump" to the interrupt service routine and then goes back to THE PROGRAM.

The program that does the magic and allows us running multiple programs "at the same time" over a single CPU is the OS.
The OS keeps a list of processes that are ready to run, with all the information needed -- their priorities, their memory regions, the point in the code where they stopped, etc.

Every now and then a timer interrupt is received causing the scheduler (which is part of the OS) to run. The scheduler registers the process that was currently running as "stopped" and chooses one of the waiting processes, restoring its meta-date (stack, etc.), and jumps to the point where that process stopped last time.

This gives you the illusion of running multiple processes simultaneously. But at the bottom of it, there is only one program that runs -- the OS -- and it gives priority to (or, calls) user loaded programs.

Regarding your question about inra-process communication. Again, this is usually done via methods provided by the OS. When a process waits for a signal it calls an OS method that registers this process awaits a signal and blocks the processes, allowing other processes to run. When the other process  needs to send data to the first processes it uses a OS method that records the data and its destination, and (eventually) awakes the destination process. From the point of view of the first process it got blocked on a OS function which returns only when new information arrives.


Using analog values with Algebraic Normal Form? Algebraic normal form (ANF) is a way of describing digital circuits made up of AND and XOR gates.

The below is an example of an ANF expression which evaluates to true if two or more of it's three inputs are true ($\oplus$ being XOR, implicit multiplication being AND)

$x_0x_1 \oplus x_0x_2 \oplus x_1x_2$

When a digital circuit is expressed this way, you can evaluate it as a polynomial, taking 1 or 0 as inputs for the variables, doing a multiplication for an AND gate, addition for an XOR gate, and doing a modulus by 2 on the final result.

$y = x_0x_1 + x_0x_2 + x_1x_2$

you can verify a truth table by plugging in 0s and 1s for the various $x$ parameters and seeing that it comes out to the correct values.

What I'm curious about is what if we don't use whole numbers?  I'm sure that's a well studied thing but I haven't been able to find any information about it.

it seems sort of like fuzzy logic, but fuzzy logic is a well defined thing with different operations.

Here's some values plugged in and their output.

\begin{array}{|c|c|c|c|}
\hline
x_0 & x_1 & x_2 & output & output \% 2 \\
\hline
0 & 0 & 0 & 0 & 0 \\
1 & 1 & 0 & 1 & 1 \\
1 & 1 & 1 & 3 & 1 \\
0.5 & 0.5 & 0 & 0.25 & 0.25\\
0.9 & 0.9 & 0.9 & 2.43 & 0.43 \\
1.0 & 1.0 & 0.5 & 2.0 & 0.0  \\
\hline
\end{array}

The analog value input gives output that seems especially wrong in the last two rows.

It seems like maybe this just "doesn't work", but it also feels like maybe it does work, or does do something interesting, perhaps with some modifications?

Has anyone come across non digital values used in ANF or similar?

Thanks!

Perhaps the most appropriate way of thinking of algebraic normal form is as the following statement:

  Every function from $\mathbb{Z}_2^n$ to $\mathbb{Z}_2$ can be represented uniquely as a multilinear polynomial.

Here $\mathbb{Z}_2$ is the field with two elements, and a polynomial is multilinear if all monomials are products of distinct variables (so you can't have $x_i^2$ in a monomial).

The upshot is that the modulo 2 operation is not the most natural way of understanding the computation involved in algebraic normal form; rather, addition is done over the field $\mathbb{Z}_2$. It seems rather unnatural to apply the modulo 2 operation to real numbers in this context.

One generalization of algebraic normal form to real numbers is the Fourier expansion over the Boolean cube:

  Every function from $\{-1,1\}^n$ to $\mathbb{R}$ can be represented uniquely as a multilinear polynomial (with real coefficients).

Here $\mathbb{R}$ is the field of real numbers.

Another generalization is the Hermite expansion in Gaussian space:

  Every function from $\mathbb{R}^n$ to $\mathbb{R}$ can be approximated arbitrarily well by a polynomial (with real coefficients).

Here arbitrarily well means up to $\epsilon$ distance in $L^2$ with respect to Gaussian measure (e.g., see this Wikipedia article).


Partition array into k subsets We are given an array and a number K. Partition array into K subsets such that

let MaxSum be the maximum sum of among subsets.

We have to minimize summation =$$\sum_{i=1}^{k}MaxSum-sum(i) $$

Is this problem polynimial time solvable?

I'm assuming by $sum(i)$ you mean that given an ordering of the $k$ partitioned subsets, sum over all elements of the $i$th subset.

The $k=2$ case is the optimization variant of the set partitioning problem (https://en.wikipedia.org/wiki/Partition_problem) which is known to be as hard as subset sum. EDIT: The general case is as difficult by reduction from $k=2$.


If P is equal to NP, then what happens to the problems those can be solved in polynomial time? Suppose that an algorithm $A$ is able to solve a problem in NP in polynomial time.
Does this effect the good old sorting, searching, shortest path, minimum spanning tree etc. algorithms?
Can this improvement pave the way for a $O(n)$ sort or $O(log^*n)$ search?

Edit: P vs. NP problem can also be interpreted as "can we find something without searching?" that's why I wonder if that effects the other problems as well.

First of all, it is not clear what you mean by an algorithm which is able to solve any problem in NP; usually one algorithm solves one problem. However, given a polynomial time algorithm for solving some NP-complete problem, you can solve any NP problem in polynomial time. However, every problem will require a different algorithm.

This doesn't necessarily affect problems which are already in P. Indeed, we have unconditional lower bounds on search and sort which show that no $O(n)$ sort or $O(\log^* n)$ search algorithm exist, in restricted computation models. Even when tight bounds are not available (or when you consider a computation model for which good lower bounds are not available), there is no reason to assume that an algorithm for NP-complete problems is relevant.

On the other hand, if P=NP then more difficult problems are affected: you can show using a padding argument that P=NP implies EXP=NEXP, for example. But the implication doesn't go the other way around.


Quicksort Partitioning: Hoare vs. Lomuto There are two quicksort partition methods mentioned in Cormen:

(the argument A is the array, and [p, r] is the range, inclusive, to perform the partition on. The returned value is the index to the pivot after the partition.)

Hoare-Partition(A, p, r)
x = A[p]
i = p - 1
j = r + 1
while true
    repeat
        j = j - 1
    until A[j] <= x
    repeat
        i = i + 1
    until A[i] >= x
    if i < j
        swap( A[i], A[j] )
    else
        return j

and:

Lomuto-Partition(A, p, r)
x = A[r]
i = p - 1
for j = p to r - 1
    if A[j] <= x
        i = i + 1
        swap( A[i], A[j] )
swap( A[i + 1], A[r] )
return i + 1

Disregarding the method of choosing the pivot, in what situations is one preferable to the other?  I know for instance that Lomuto preforms relatively poorly when there is a high percentage of duplicate values ( i.e. where say more than 2/3rds the array is the same value ), whereas Hoare performs just fine in that situation.

What other special cases make one partition method significant better than the other?

Pedagogical Dimension

Due to its simplicity Lomuto's partitioning method might be easier to implement. There is a nice anecdote in Jon Bentley's Programming Pearl on Sorting:

  “Most discussions of Quicksort use a partitioning scheme based on two approaching indices [...] [i.e. Hoare's]. Although the basic idea of that scheme is straightforward, I have always found the details tricky - I once spent the better part of two days chasing down a bug hiding in a short partitioning loop. A reader of a preliminary draft complained that the standard two-index method is in fact simpler than Lomuto's and sketched some code to make his point; I stopped looking after I found two bugs.”

Performance Dimension

For practical use, ease of implementation might be sacrificed for the sake of efficiency. On a theoretical basis, we can determine the number of element comparisons and swaps to compare performance. Additionally, actual running time will be influenced by other factors, such as caching performance and branch mispredictions.

As shown below, the algorithms behave very similar on random permutations except for the number of swaps. There Lomuto needs thrice as many as Hoare!

Number of Comparisons

Both methods can be implemented using $n-1$ comparisons to partition an array of length $n$. This is essentially optimal, since we need to compare every element to the pivot for deciding where to put it.

Number of Swaps

The number of swaps is random for both algorithms, depending on the elements in the array. If we assume random permutations, i.e. all elements are distinct and every permutation of the elements is equally likely, we can analyze the expected number of swaps.

As only relative order counts, we assume that the elements are the numbers $1,\ldots,n$. That makes the discussion below easier since the rank of an element and its value coincide.

Lomuto's Method

The index variable $j$ scans the whole array and whenever we find an element $A[j]$ smaller than pivot $x$, we do a swap. Among the elements $1,\ldots,n$, exactly $x-1$ ones are smaller than $x$, so we get $x-1$ swaps if the pivot is $x$.

The overall expectation then results by averaging over all pivots. Each value in $\{1,\ldots,n\}$ is equally likely to become pivot (namely with prob. $\frac1n$), so we have

$$
\frac1n \sum_{x=1}^n (x-1) = \frac n2 - \frac12\;.
$$

swaps on average to partition an array of length $n$ with Lomuto's  method.

Hoare's Method

Here, the analysis is slightly more tricky: Even fixing pivot $x$, the number of swaps remains random.

More precisely: The indices $i$ and $j$ run towards each other until they cross, which always happens at $x$ (by correctness of Hoare's partitioning algorithm!). This effectively divides the array into two parts: A left part which is scanned by $i$ and a right part scanned by $j$.

Now, a swap is done exactly for every pair of “misplaced” elements, i.e. a large element (larger than $x$, thus belonging in the right partition) which is currently located in the left part and a small element located in the right part.
Note that this pair forming always works out, i.e. there the number of small elements initially in the right part equals the number of large elements in the left part.

One can show that the number of these pairs is hypergeometrically $\mathrm{Hyp}(n-1,n-x,x-1)$ distributed: For the $n-x$ large elements we randomly draw their positions in the array and have $x-1$ positions in the left part.
Accordingly, the expected number of pairs is $(n-x)(x-1)/(n-1)$ given that the pivot is $x$.

Finally, we average again over all pivot values to obtain the overall expected number of swaps for Hoare's partitioning:

$$
\frac1n \sum_{x=1}^n \frac{(n-x)(x-1)}{n-1} = \frac n6 - \frac13\;.
$$

(A more detailed description can be found in my master's thesis, page 29.)

Memory Access Pattern

Both algorithms use two pointers into the array that scan it sequentially. Therefore both behave almost optimal w.r.t. caching.

Equal Elements and Already Sorted Lists

As already mentioned by Wandering Logic, the performance of the algorithms differs more drastically for lists that are not random permutations.

On an array that is already sorted, Hoare's method never swaps, as there are no misplaced pairs (see above), whereas Lomuto's method still does its roughly $n/2$ swaps!

The presence of equal elements requires special care in Quicksort.
(I stepped into this trap myself; see my master's thesis, page 36, for a “Tale on Premature Optimization”)
Consider as extreme example an array which filled with $0$s. On such an array, Hoare's method performs a swap for every pair of elements - which is the worst case for Hoare's partitioning - but $i$ and $j$ always meet in the middle of the array. Thus, we have optimal partitioning and the total running time remains in $\mathcal O(n\log n)$.

Lomuto's method behaves much more stupidly on the all $0$ array: The comparison A[j] <= x will always be true, so we do a swap for every single element! But even worse: After the loop, we always have $i=n$, so we observe the worst case partitioning, making the overall performance degrade to $\Theta(n^2)$!

Conclusion

Lomuto's method is simple and easier to implement, but should not be used for implementing a library sorting method.


Simplest combination of logic gates to produce a given set of outputs Given a truth table for a truth function that takes n inputs and produces a single output (true or false), what is the fastest way to find the simplest combination of logic gates that will output the given truth table?

A few rules for specificity:

Any binary truth function may be used as a logic gate. In other words, AND, OR, XOR, NOR, and NAND are all valid logic gates, but a binary truth function like AND(NOT(A), B) also counts as a single logic gate when determining the simplicity or complexity of a solution.
The "simplest" solution is the one which uses the fewest logic gates
The output of a logic gate may either be the output, or it may be an input to exactly one other logic gate.

Primary inputs themselves may go to more than one logic gate; it is only the output of a logic gate that may only be used once. I am most concerned with the minimal circuit necessary for the binary multiplication of two numbers. Do we know of a minimal circuit for multiplication? If so is there an efficient algorithm to construct the minimal circuit?

This problem is discussed in Circuit Minimization Problem, by V. Kabanets and J.-Y. Cai.

Obviously the decision version is in NP (does there exists a circuit of size $\le k$ which agrees with the given truth table), since you could provide the circuit $\mathcal{C}$ and verify that $\forall x\in\left\{0,1\right\}^n : \mathcal{C}(x)=f(x)$. This can be done in polynomial time (relative to the input's size), since the size of the truth table is $2^n$.

It's an open question how hard the problem is.  The above paper shows that any proof that this problem is in $P$, or any proof that it is $NP$-complete, would extend our current knowledge and imply a solution to long-standing open problems in complexity theory.

If the Circuit Minimization Problem is in $P$, then it is shown that $BPP=ZPP$ (so for now, showing your problem is in $P$ is open).

Since this is believed to happen anyway (under the assumption that $P=BPP$), they give more consequences which are less likely. For example, it is enough to show $2^n/n$ circuit lower bound for the class $E$ to obtain a $2^{c\cdot n}$ lower bound (If high circuit complexity functions exist in $E$, then very high circuit complexity functions exist too). They also show how to factor Blum integers efficiently on average (Which, they say, is the strongest evidence for the fact that this problem lies outside of $P$).

If the Circuit Minimization Problem is $NP$-hard (under what they call a "natural reduction", where the reduction's output size depends only on the input's size and not structure) then $BPP\subseteq SUBEXP$ and $BPP=P$ unless the exponential time hypothesis fails.


How do I compute this non terminal positions evaluation, for tic-tac-toe? Looking at this solution on page 3 but having trouble understanding the evaluation function specifically.

  For non terminal positions, we use a linear evaluation function
  defined as

  Eval (s) = 3[X2(s)]+X1(s)−(3[O2(s)]+O1(s))

  We define X n ( s ) as the number of rows, columns, and diagonals in
  state s with exactly n X’s and no O’s, and similarly define O n ( s )

Looking at this state 's' for example (these problems accounts for symmetry):

|X| | |
| |O| |
| | | |

It shows an evaluation of -1

However, got 0:

X2(s) = 0 because there are no rows or columns with 2 X's.
X1(s) = 2 because the top row and left column both have 1 X (but the diagonal has an O)

O2(s) = 0 because there are no rows or columns with 2 O's.
O1(s) = 2 because the middle row and middle column both have 1 O (but the diagonal has an X)

Plugging in:

0+2 - (0+2) = 0

So, I thought I am missing symmetry but I just get a bigger scale that still = 0's.

I must be overlooking something simple but not sure.

Any help is appreciated.


Making a CFG for a^i b^j c^k such that i+j = 3k I have the language $L = \{a^i b^j c^k \mid i+j=3k\}$, however I am struggling to convert it to a CFG.

I have made it into a PDA fairly easily, its just now getting this to the CFG which is the issue.

I have thought about dividing it into 3 cases then taking the union of them for example:

$i=0, j=3k$

$i=3k, j=0$

But this still hasn't gotten me very far

Any help would be appreciated
Thanks

I am not sure whether it is a good idea to actually provide the grammar here in an answer but since the grammar is actually fairly easy I cannot see which details I could hide in a hint, so here it is:

$G = (\{S, A\}, \{a, b, c\}, P, S)$ with
$$
P = \{S \to aaaSc \mid aabAc \mid abbAc \mid bbbAc \mid \varepsilon, A \to bbbAc \mid \varepsilon\}.$$
You start by adding three $a$s for each $c$, after finitely many (possibly 0) applications of the first rule, you start creating three $b$s for each $c$ but one time you may actually add 2 $a$s, 1 $b$ for one $c$ or 1 $a$, 2 $b$s for one $c$ (2nd and 3rd rule, respectively).


Unreachable Real Numbers - Randomness & Computability I've recently read that there were many real numbers that would never be reachable by humanity. The explanation itself says that we can write as many programs as integers which is infinite, but there are infinite real numbers between two integers so Real numbers infinity is bigger than integer numbers.

Well my question is, couldn't we overpass this limitation by writing a program that prints out a random number in every execution? I know this is not a warranty that every real number would be printed but at least they would all have a chance.

Please point out if my reasoning is wrong and why.

Thanks you all very much!

In a nutshell: Printing a random non-computable real is a meaningless task, for precise technical reasons. The meaningful problem is to print non-computable numbers precisely identified by some unique property. But these cannot be printed by any program precisely because they are not computable. Using randomness in the hope of printing by chance the uncomputable
number you are interested in is impossible with a program, unless you use a physical random
phenomenon as randomness source (depending on physics, with probability zero, and without knowing whether you are succeeding).

I am not sure what you mean by a number that is not "reachable by
humanity".

The fact that there is an infinity of real numbers between two
integers does not imply that there are more real numbers than
integers (though there are more).

For example, there is an infinity of rational number between two
integers, but the number (cardinality) of integers and rational
numbers is the same. Actually, there is an infinity of rational
numbers between any two rational numbers, but it does not imply that
there are more rational numbers than rational numbers.

By the way, there is an infinity of rational numbers between any two real
numbers, but there are more real numbers than rational numbers.

That should at least tell you that determining which set is bigger is
not at all obvious, and is not related to the number of angels who can
dance between two numbers.

Then why are there more real numbers than integer? Here is one of the
proofs due to Cantor. The reals in the interval $[0.0, 1.0[$ are isomorphic
to infinite sequences of the symbols 0 and 1, which is their
representation in binary notation (by just adding a decimal/binary point in
front). If you consider any enumeration of these infinite strings, it
is always possible to define a string that is not in the enumeration,
by using for its $n^{th}$ symbol the opposite (1 for 0, and 0
for 1) of the $n^{th}$ symbol of the $n^{th}$ number of the
enumeration. This means that if you attempt to define a
one-one correspondance between the integers (used to enumerate) and the
reals (being enumerated) there are always reals that are not included
in the enumeration, which can be interpreted as implying that there
are more reals than integers.

This technique is a diagonalization proof, similar to the proof technique used for proving the
undecidability of the halting problem.

Now, as remarked in the question, any program texts can be read as an
integer, so that one may consider there are no more programs than
integers. This is why we may conclude that there are numbers that
cannot be computed by a program, hence cannot be printed (else, each real could be mapped to the integer corresponding to the
program that prints it.). But this
fast reasonning may not be so convincing, so lets get more into
details. and also consider an actual example.

Your printing device, assuming it does what you expect,
even if it started at the big bang, is only producing digits one by
one, and will at any time have produced only a finite number of
digits, say $n$. That only defines a rational number, and even if we
are actually printing some irrational number. Assuming we are using binary numbers,
if we have already printed $n$ digits, they correspond to a rational
number $x$, and all we know is that the number we ultimately print
will be in the interval $[x, x+2^{-n}[$. But this interval will always
contain an infinity of rational numbers, of computable real, and of
uncomputable reals. And this will remain so for any future value of $n$. Stating that you want to print an uncomputable
number, any  uncomputable number, is a meaningless endeavor.
It reminds me of people looking for the pot of gold at the foot of the rainbow.

The meaningful problem is not to write any uncomputable number, but to write a specific one,  identified by a specific property. Consider for example the binary real $h\in[0.0, 1.0[$ defined as follows: its $n^{th}$
digit is $1$ iff the Turing Machine with Gödel number $n$ halts on empty
input, and $0$ otherwise. This number is very precisely defined. But
if it were computable, we would have a way to decide the halting
problem. Hence, there is no algorithm, no program, that can enumerate the bits of
the real number $h$, and thus there is no way to print it.  And using random generators will not help.

Of course, it could be that some random generator, controlled by a
random physical process such as radioactive decay would produce
precisely that number (with a probability closing to zero as time
passes). But, at best:

1- you would have at any time only a rational number which is a prefix
    of the non-computable real you are interested in

2- you would most likely be unable to check wether your prefix is
    really correct

3- you would have no garantee that the next digit will still be correct.

But, even then, you must assume that the random generator uses some
physical "true" randomness source. Even randomly created, or
computing with whatever technique known or yet to be invented, no computer program can
print an uncomputable real number, such as the number $h$ defined above.  That
is a result of computability theory that no such program can exist.

Your only hope is that computability theory does not apply to
radioactive decay or some other such physical phenomena. But I know of no proof
either way. And it would not really help you in any meaningful way, because the probability of success is zero, and because you would have no way of knowing you are succeeding. Note that I cannot say "of knowing you have succeeded", because you never reach the end of that infinite process, so that any proof would have to be an on-going continuous process, which cannot be finitely defined for essentially the same reason a printing program cannot exist for an uncomputable number.