Why $\frac{n^3}{2^{\Omega(\sqrt{\log n})}}$ doesn't refute the lower bound $O(n^{3-\delta})$? I have a simple quesiton:

  It is conjectured that All Pairs Shortest Path (APSP) has no $O(n^{3-\delta)}$-time algorithm for any $\delta >0$ by SETH.

also

  there is a result that says APSP can be solved in time $\frac{n^3}{2^{\Omega(\sqrt{\log n})}}$ by Ryan Williams.

But, this improvement doesn't refute the conjectures.

So, what I did is as following: I compare between $\lim_{n -> \infty} \frac{( \frac{n^3}{2^{\sqrt{\log n}}})}{n^{3-\delta} } = 0 $ So, $\frac{n^3}{2^{\Omega(\sqrt{\log n})}}$ is better than the other one, so why it doesn't mean that we refute the conjecture.

When I have this function: $\frac{n^3}{2^{\Omega(\sqrt{\log n})}}$, I didn't know how to compare it with other since Big Omega is only on part of it, how to compare in general with other function when you have this one?

Thanks in advance!

It looks like the comparison in the question is wrong.

$$\begin{aligned}
\lim_{n -> \infty} \frac{\frac{n^3}{2^{\sqrt{\log n}}}}{\ \ n^{3-\delta}\ \ } &= \lim_{n -> \infty} \frac{n^{\delta} }{2^{\sqrt{\log n}}}=\lim_{n -> \infty} \frac{2^{\delta\log n} }{2^{\sqrt{\log n}}}\\
&=\lim_{n -> \infty} 2^{\delta\log n-\sqrt{\log n}}=\lim_{m -> \infty}2^{\delta m-\sqrt{m}}\\
&=\lim_{m -> \infty}2^{\sqrt m(\delta\sqrt{m} -1)}\\
&=2^{+\infty}=+\infty.\\
\end{aligned}$$

Here $\log n$ is understood as $\log_2n$. Since $\log_a n=\log_a2\cdot\log_2n$, the limit above will still be infinity if the base of $\log$ is switched to any number greater than 1.

In fact, for any constant $c>0$, however smaller it is and any constant $\delta>0$, however small it is, we still have, by similar argument,

$$\lim_{n \to \infty}\frac{\frac{n^3}{2^{c\sqrt{\log n}}}}{\ \ \ {n^{3-\delta}\ \ \ }} =+\infty.$$

  I compare between $\lim_{n -> \infty} \frac{ \frac{n^3}{2^{\sqrt{\log n}}}}{\ \ \ n^{3-\delta}\ \ } = 0 $ So, $\frac{n^3}{2^{\Omega(\sqrt{\log n})}}$ is better than the other one, so why it doesn't mean that we refute the conjecture.

To be more careful, there is another mistake in the above reasoning. Even if $\lim_{n -> \infty} \dfrac{\frac{n^3}{2^{\sqrt{\log n}}}}{\ \ n^{3-\delta}\ \ } = 0 $, it does not imply it will refute the conjecture. The point is, "APSP can be solved in time $\dfrac{n^3}{2^{\Omega(\sqrt{\log n\ })}}$" might be true because it can be solved in time $\frac{n^3}{2^{0.01\sqrt{\log n\ \ }}}$, not because it can be solved in time $\frac{n^3}{2^{\sqrt{\log n\ \ }}}$". If you want to use the fact that "APSP can be solved in time $\dfrac{n^3}{2^{\Omega(\sqrt{\log n\ })}}$" to refute the conjecture, you have to show that

$$O(n^{3-\delta}) \cap \frac{n^3}{2^{\Omega(\sqrt{\log n})}} = \emptyset,$$
or, in plain words, there is no function $f\in \Omega(\sqrt{\log n})$ such that $\dfrac{n^3}f\in O(n^{3-\delta})$.

Well, in fact, the other extreme is true. $\dfrac{n^3}f\in O(n^{3-\delta})$ for all $f\in \Omega(\sqrt{\log n})$.


Evasiveness of acyclicity of undirected graph The lecture note by Jeff Erickson discusses "Evasive Graph Properties":

  We call a graph property evasive if we have to look at all $\binom{n}{2}$ entries in the adjacent matrix to decide whether an (undirected) graph has that property.

As an example, it shows that connectivity is evasive.

I want to know: Is acyclicity evasive? How to prove/disprove it?

My attempt: A rather straightforward adaptation I made from the proof for connectivity does not work for acyclicity.

Consider any algorithm for acyclicity. We will use the following adversary:

  Whenever the algorithm asks for an edge, say that the edge exists if it connects two different connected components. (That is, if it doesn't close a cycle.)

You can show that the graph constructed by this dialog is always a forest, and moreover the constructed graph has the same connected components as the query graph (which contains all queried edges). In particular, when the last edge is asked, the graph is a tree (assuming $n \geq 3$; otherwise every graph is acyclic), and the graph is acyclic if and only if this edge does not belong to the graph.


How to understand the analysis of expected running time of randomized quick-sort in this paper? I'm learning the book named Data Structures & Algorithms in Python.

On Page 557-558, there is a proof of the expected running time of randomized qucick-sort. I have some problems confusing me some days. I will note them in bold form.

Here's orginal text:

  Proposition 12.3: The expected running time of randomized quick-sort on a sequence $S$ of size $n$ is $O(n \log n)$.

  Justification: We assume two elements of $S$ can be compared in $O(1)$ time. Consider a single recursive call of randomized quick-sort, and let $n$ denote the size of the input for this call. Say that this call is “good” if the pivot chosen is such that subsequences $L$ and $G$ have size at least $\frac{n}{4}$ and at most $\frac{3n}{4}$ each; otherwise, a call is “bad.”

  Now, consider the implications of our choosing a pivot uniformly at random. Note that there are $\frac{n}{2}$ possible good choices for the pivot for any given call of size n of the randomized quick-sort algorithm. Thus, the probability that any call is good is $\frac{1}{2}$. Note further that a good call will at least partition a list of size $n$ into two lists of size $\frac{3n}{4}$ and $\frac{n}{4}$, and a bad call could be as bad as producing a single call of size $n−1$.

  Now consider a recursion trace for randomized quick-sort. This trace deﬁnes a binary tree, $T$, such that each node in $T$ corresponds to a different recursive call on a subproblem of sorting a portion of the original list.

  Say that a node $v$ in $T$ is in size group $i$ if the size of $v$’s subproblem is greater than $\left(\frac{3}{4}\right)^{i+1}n$ and at most $\left(\frac{3}{4}\right)^in$ Let us analyze the expected time spent working on all the subproblems for nodes in size group $i$. By the linearity of expectation (Proposition A.19), the expected time for working on all these subproblems is the sum of the expected times for each one. Some of these nodes correspond to good calls and some correspond to bad calls. But note that, since a good call occurs with probability $\frac{1}{2}$, the expected number of consecutive calls we have to make before getting a good call is $2$.

  ⓵ Moreover, notice that as soon as we have a good call for a node in size group $i$, its children will be in size groups higher than $i$.

  ⓶ Thus, for any element $x$ from the input list, the expected number of nodes in size group $i$ containing $x$ in their subproblems is $2$. In other words, the expected total size of all the subproblems in size group $i$ is $2n$.

  Since the nonrecursive work we perform for any subproblem is proportional to its size, this implies that the total expected time spent processing subproblems for nodes in size group $i$ is $O(n)$.

  The number of size groups is $\log_{\frac{4}{3}}n$, since repeatedly multiplying by $\frac{3}{4}$ is the same as repeatedly dividing by $\frac{4}{3}$. That is, the number of size groups is $O(\log n)$. Therefore, the total expected running time of randomized quick-sort is $O(n\log n)$. (See Figure 11.13.)

Here are my problems:

According this sentence:

  ⓵ Moreover, notice that as soon as we have a good call for a node in size group $i$, its children will be in size groups higher than $i$.

Which size group does node $s(a)$ belong to? And why?

  ⓶ Thus, for any element $x$ from the input list, the expected number of nodes in size group $i$ containing $x$ in their subproblems is $2$. In other words, the expected total size of all the subproblems in size group $i$ is $2n$.

I can't really understand the meaning of this sentence.

The root node corresponds to a subproblem of size $n$. This is larger than $(3/4)^1 n$ and at most $(3/4)^0 n$, so the root node lies in group $0$.

Given any element $x$ and any integer $i$, the expected number of subproblems of group $i$ containing $x$ is at most $2$. This is because if $P$ is a subproblem of group $i$ containing $x$ and $Q$ is its child subproblem containing $x$, then $Q$ is of group $i+1$ with probability at least $1/2$. (Some calculation is needed here.)

Linearity of expectation shows that the expected total size of all subproblems of group $i$ is at most $2n$ — we get this by summing the expected number of subproblems of group $i$ containing $x$ over all possible elements. (You can only understand this if you know what linearity of expectation is.)


A key-value datastructure with fast (on average) member move and nearest neighbors search? I have a 3 dimensional float key search space (say a simulation world). I want to keep my values (ints, agent ids) in a data structure that can perform nearest neighbors search (with search for N neighbors in a range surrounding a given key) as fast as possible in terms of search algorithmic complexity (on average). Also I need a fast (on average) remove-insert or key update mechanism in that datastructure. I wonder what is such structure?

An octree or k-d tree are standard data structures for this sort of task, and should provide reasonably efficient support for all of the operations you listed.


Karatsuba multiplication on numbers with odd length I am learning about Karatsuba-Ofman multiplication. I don't quite understand how to multiply two numbers with odd length.

Let's take two 3-digit numbers $a = 234; b = 857$ with base $B = 10$ and length $n=3$.

The first step is to split split $a$ and $b$ at position $n/2$. However, since $n=3$ where do I split it? Does it even matter?

Later in the algorithm I have to multiply $((a_1 + a_0) \cdot (b_1 + b_0) - (a_1 \cdot b_1) - (a_0 \cdot b_0)) \cdot B^{n/2}$. Would that mean, with $n=3$, I have to multiply by $B^{1.5}$?

Here, $B = 10$ and $n = 3$. The Karatsuba method works for any $m < n$. With $m = 2$ :

$a = 2 * 10^2 + 34$
and
$b = 8 * 10^2 + 57$
; thus, $a_1 = 2$, $a_0 = 34$, $b_1 = 8$ and $b_0 = 57$.

It follows that $ab = z_2 B^{2m} + z_1 B^m + z_0$ where $z_2 = a_1 b_1 = 16$, $z_1 = a_1 b_0 + a_0 b_1 = 386$ and $z_0 = a_0 b_0 = 1938$.

Thus, $ab = 16 \cdot 10^{2*2} + 386 \cdot 10^2 +  1938 = 200538$.

I'm not sure about the step you mentioned, as it doesn't seem to give the correct result with the current decomposition ($m = 2$).


perspective transformation of a grid A perspective transformation of a point is defined as follows:

$ x' = \frac{M_{11}x + M_{12}y +M_{13}}{M_{31}x + M_{32}y +M_{33}} $

$ y' = \frac{M_{21}x + M_{22}y +M_{23}}{M_{31}x + M_{32}y +M_{33}} $

Now, say I wish to transform a uniform grid (blue) and obtain the transformed grid (green), as illustrated below.

My intuition tells me that the largest transformed tile (on the green grid) will  be either in the top left, top right, bottom left or bottom right corners i.e. in one of the extreme corners.

Is there a (not necessarily formal) way to prove this?

We can apply a linear transformation to get into the situation
$$
\begin{align*}
x' &= \frac{x+C}{Ax+By+1} \\
y' &= \frac{y+D}{Ax+By+1}
\end{align*}
$$
The Jacobian of the mapping
$$
J = \begin{vmatrix} \frac{\partial x'}{\partial x} & \frac{\partial x'}{\partial y} \\ \frac{\partial y'}{\partial x} & \frac{\partial y'}{\partial y} \end{vmatrix}
$$
is the infinitesimal area element of the mapping. That is, it is the area of an epsilonic rectangle around the image of a point $(x,y)$.
In our case, the Jacobian turns out to be
$$
J(x,y) = \frac{1-AC-BD}{(Ax+By+1)^3}.
$$
This function is either increasing or decreasing in each of the inputs $x,y$, and so after the initial affine transformation, one of the corner rectangles has the maximal area (and same for the minimal area). The linear transformation might change the sense of the axes, but otherwise only affects the area by a constant factor.


Is it possible to create a human thinking and acting program on a computer? Does Artifical Intelligence need something else, something that is not so limited as a computer to achieve the goal of building a humanly thinking and acting program?

If so, what might this be? I don't know much about quantum computers, but might they be a solution?

Quantum computers have the same power as classical computers, only they can apparently solve some problems much faster. In order to simulate a human, you need to consider two aspects:

Cognitive aspect: The program should behave like a human being.
Physical aspect: The object should look like a human being.

Turing suggested a way of sidestepping the second issue. He suggested limiting the interaction to a text-based "chat". Even in this case, the computer has to careful regarding reaction times: the computer can presumably type faster than a human and perform calculations faster.

There are several variants of the Turing test, but one of them involves many testers and two interviewees: a bona fide human and a computer. The computer is trying to pass as human. An interviewer gets assigned either the human or the computer, and should guess which is which. The computer passes the Turing test if the interviewer guesses no better than a random coin toss.

Current computers are not able to pass the Turing test. Whether they could potentially pass the test is at this point a philosophical and religious question. One advantage that humans have over computers is their large brain and their long learning period. However, if we could build large enough computers, so far we don't understand the algorithmic behavior of the brain, and so cannot mimic it. Artificial intelligence tries to ape human intelligence using different "hardware". Whether this approach can be successful or not is not clear.

In the past few decades, focus has switched from trying to emulate the brain to trying to solve certain tasks, such as translation. Modern techniques use statistical tools that are not aimed at mimicking behavior but only at mimicking competence. This approach works much better than earlier approached which did try to understand what human cognitive processes are based on. Perhaps this approach is hopeless if the goal is passing the Turing test.

So what is missing for artificial intelligence to succeed? Higher processing power? Computation techniques mimicking brain functions? Mechanisms like the Universal Grammar which might be hiding in our genes? Nobody knows. But for many people, there is no theoretical barrier, only practical ones.


Prove Lecture Planning is NP-complete This is a practice problem from my algorithms class. (And no, it was not assigned as homework. I can't prove this, but you don't have to answer if you don't believe me.) To me this seems like a very difficult problem to show NP-completeness for since due to its abundance of features, it's tricky to mold a known NP-complete problem into it.

  You’ve been asked to organize a freshman-level seminar. The plan is to have the first portion of the semester consist of a sequence of $l$ guest lectures by outside speakers, and have the second portion of the semester devoted to a sequence of $p$ hands-on projects that the students will do. There are $n$ options for speakers overall, and in week number $i$ (for $i = 1, 2, \ldots, l$) a subset $L_i$ of these speakers is available to give a lecture. On the other hand, each project requires that the students have seen certain background material in order for them to be able to complete the project successfully. In particular, for each project $j$ (for $j = 1, 2, \ldots , p$), there is a subset $P_j$ of relevant speakers so that the students need to have seen a lecture by at least one of the speakers in the set $P_j$ in order to be able to complete the project. So this is the problem: Given these sets, can you select exactly one speaker for each of the first $l$ weeks of the seminar, so that you only choose speakers who are available in their designated week, and so that for each project $j$, the students will have seen at least one of the speakers in the relevant set $P_j$. We’ll call this the Lecture Planning Problem.
  Prove that Lecture Planning is NP-complete.

I should note that it isn't explicitly stated in the problem, but I'm assuming that a speaker can only give at most one talk. (But if this seems to prevent the problem from being NP-complete, let me know.)

At first I tried solving some graph-based problems (e.g., Independent Set) using Lecture Planning, but wasn't able to proceed because I'm not sure how you would partition vertices into subsets $L_i$ or $P_j$.

Thus I decided to go to 3-SAT. Even then, it is not obvious how you would solve 3-SAT using this setup. E.g., what would the clauses be? My first thought was they could be the $l$ subsets $L_i$, and you would need a variable to be true in each; this would correspond to picking a speaker for that week. But then how do you incorporate the $P_j$ so as to ensure the formula is satisfied (if satisfiable)?

Also thought about making the clauses the $P_j$, but again, this didn't really seem to work.

I would greatly appreciate a hint. Thanks!

Hint 1: For a SAT problem instance with $n$ variables construct a planning problem with $n$ lectures

Hint 2: Each $L_i$ will have $2$ elements

Hint 3: Clauses will be $P_j$, as you have already guessed.


Generation of random binary trees Given n, I want to randomly generate a binary tree (unlabelled) that has n end nodes. Could someone kindly provide a reference containing an algorithm for doing that?

I attempted to do as follows: From a PRNG obtain n PRNs in [0.0, 1.0) as (relative) frequencies of n symbols for generating a Huffman tree (used in data compression). But, if the PRNs used are uniform, then I think this would highly favour generation of those Huffman trees that are more flat and Huffman trees corresponding to widely different frequencies of the symbols would be highly suppressed in the generation process. If this is correct, how could one do better? Thanks in advance.

Binary trees are counted by Catalan numbers: the number of "full" binary trees (each node has either 0 or 2 children) with $n$ leaves is $C_{n-1}$. The Catalan numbers are given by an explicit formula, and also satisfy the recurrence
$$ C_{n+1} = \sum_{i+j = n} C_i C_j, $$
which follows directly from the interpretation as counting binary trees. You can use this formula to decode a number in $[0,C_{n-1}) = \{0,\ldots,C_{n-1}-1\}$ to a binary tree. If the index is chosen randomly, you obtain a random binary tree.

The decoding procedure is recursive. First, we partition $[0,C_{n-1})$ into intervals of lengths $C_0 C_{n-2}, C_1 C_{n-3}, \ldots, C_{n-2} C_0$. If the number falls in the interval of length $C_i C_j$, then the left subtree will have $i+1$ leaves, and the right subtree will have $j+1$ leaves. Within the interval, we have an index in the range $[0,C_i C_j)$, which we decode to a pair of indices $x \in [0,C_i)$ and $y \in [0,C_j)$. We recursively compute which tree with $i+1$ leaves is encoded by $x$ and which tree with $j+1$ leaves is encoded by $y$. The recursion stops when $n = 1$, in which case the tree consists of just the root.


Comparing variable image to static image What are Levenshtein distance algorithms, but for images?

I will have one static image (the target: what it should look like) and one variable image (actual: what the user has created)

For example,

Target:

The following should be classified as "close enough"

Actual:

But the following should be classified as "incorrect" (even though it has 2 strokes and fills the '|' part)

I will be using this as a guide for users new to the English alphabet to practice on writing.

I will, of course, have other checks in place such as counting the number of strokes made (2 for 'K', 1 for '|', 1 for '<') and also checking to see if the area covered is reasonable (filling whole area should not be identified as "correct").

The user "drawing" will only be in black and white (not greyscale).

I suppose I could train a neural network (like handwriting recognition) but only to identify if it is "close enough". I think this is overkill as this only requires checking to see if it matches a single image and not selecting the best-matching image from a set.

I think you're really asking for a distance metric on images.  Based on  your examples, I would suggest the L2 distance (sum of squares of differences in pixel intensities) or L1 distance; possibly after aligning the images.  This looks like it should b effective for the examples you list.


Why is integer programming more difficult than (real) linear programming? Why is integer programming (IP) more difficult than (real) linear programming (LP)?

I searched a lot on the web, but I didn't find an answer.

Given a starting solution, the Simplex algorithm will systematically find solutions with better values of your goal function. However, it runs using real numbers (or rational numbers). You can use the Simplex algorithm to find a solution for an integer programming problem that is optimal, except that it ignores the need for integer values.

Lets say you have a solution where a variable x has a value of x = 1000.525. Clearly that's not an acceptable solution. So you take your system, make two copies, and in one copy you add the condition x ≤ 1000, in the other you add the condition x ≥ 1001. You solve both copies of the problem, but then you have other non-integer values and you go on.

So starting with your non-integer solution, you have many, many ways to try to turn them into integer solutions.

The smaller the numbers, the worse it gets. In that example I gave, you'd expect that the solution doesn't change a lot. If you have a solution x = 0.7, you add the equation x = 0 or x ≥ 1, and that can make a massive change.


Minimum Spanning Tree with one particular edge minimised(continued) I have recently encountered a coding problem, specifically, the CCC problem S4.

In the problem, it states that you are given a spanning tree, or otherwise a "valid plan of pipes", that connect each and every home to one another. However, the tree is not the minimum spanning tree. You may use an enhancer, in exact words, with power D, to reduce the weight of one edge to what is max(0,weight-D). You have a number of days to make the given spanning tree a minimum spanning tree. During these days, you may deactivate any edge of the given spanning tree, and activate another edge of your choice. It does not matter if the tree is not a spanning tree in the process, however, at the end, it should be. You also want to minimize the amount of days you need to do this.

I have been struggling with the problem for a long time, and I cannot find any solution. I am able to find the minimum spanning tree, but I am struggling with the implementation of the enhancer.

I would appreciate any help to my problem, and sample codes will be even better.

I asked a similar question here as well:
Minimum spanning tree such that one edge can be minimised

Run Kruskal's algorithm on the weighted graphs of all buildings as vertices and all pipes with original costs as edges with weights,  with the following modification. When we are going to select the next edge (pipe) whose weight (cost) is minimum among the available edges, we choose one among the active pipes first if there is such a pipe.

At end of the algorithm, we obtain a minimum spanning tree $T$ with weights $w_1\le\cdots w_{N-2}\le w_{N-1}=m$. The number of days needed to implement $T$ as the new active pipes, denoted $p$, is the number of pipes in $T$ that are not currently active.

With the enhancer used, the total minimal cost becomes $w_1+w_2+\cdots+w_{N-2}+s(w_{N-1})$, where $s$ is the function such that $s(w)=0$ for $w\le D$ and $s(w)=w-D$ otherwise. That formula is shown in the linked question and its answers.

Can we reduce the number of days from $p$ to $p-1$?

Claim 1. If $D\le m$, then the number of days cannot be reduced to $p-1$.

The proof of claim is left to readers as a (not immediate) exercise.

So let us run Kruskal's algorithm again from scratch, with a further modification. Immediately after we have tried selecting all pipes of cost $m$ that were active (there might be none of them), we will continue to try selecting all pipes that cost more than $m$ but no more than $D$ one by one. If it is successful at least once, that is, if such a pipe will connect two disconnected components, then we will include it in the plan and we will reduce the required days by one to $p-1$. Otherwise, the required days is $p$.


RAM BSS model based (or its variant) computer recognizing Boolean languages Can any RAM BSS model based machine, or machines which are variants, recognize boolean languages(languages such as P, NP, or the like)? If so which languages are recognizable by RAM/BSS nachines, or its variants?(A variant could be to allow comparison. Or a RAM/BSS with weaker assumptions).

Christine Gaßsner studied the question you are asking. These papers seem relevant, but you should have a look at her list of publications (DBLP):

The Separation of Relativized Versions of P and DNP for the Ring of the Reals. J. UCS 16(18): 2563-2568 (2010)
Oracles and Relativizations of the P =? NP Question for Several Structures. J. UCS 15(6): 1186-1205 (2009)
Relativizations of the P =? DNP Question for the BSS Model

You seem to be asking a basic question, namely: can BSS RAM machines recognize any boolean languages? Well, a BSS machine always has some kind of comparison operator, at the very least $<$ on real numbers. We can use it to decide equality of $0$ and $1$, from which it follows that a BSS machine can recognize at least all the languages that an ordinary RAM machine can. The more interesting question is whether it can do more than that, or perhaps more efficiently.


Are all compilers Turing Machines? So the definition of a compiler I got is that:

  A compiler takes a string as input and checks if that string is syntactically correct, then outputs "Yes" or "No".

So does that mean all compilers are Turing Machines?

No, a compiler takes as string as input and checks if that string is syntactically correct. If it is, it outputs another string (code in a different language, e.g., machine code) that is equivalent to the input; if it is not, it outputs "syntax error".

A Turing machine is an abstract machine (i.e., a description of a machine, rather than an actual physical thing) that performs computations. According to the Church–Turing thesis, anything that can be computed by any physical system can be computed by a Turing machine.  Since compilers are implemented on physical systems, one could, in principle, design a Turing machine that computes the same mapping from strings to strings as any given compiler.  But it's not true that a compiler is a Turing machine; rather, a compiler does something that a Turing machine can also do.


Are type abstraction values and universal types not for non functions, but only for functions? In Types and Programming Languages by Pierce, Chapter 23 Universal Types has a summary of System F in the following figure, in particular, "type abstraction values" and their types "universal types".

In all the examples I have seen so far in the chapter, in particular Section 23.4 Examples, (not sure if I miss any example):

all the type abstraction values are parametrically polymorphic functions, by allowing the types of their arguments to have any type, and
all the universal types, i.e. the types of type abstraction values, are types of parametrically polymorphic functions.

Are type abstraction values and their universal types not for  non functions, but only for  functions?

More specifically, in any type abstraction value, say $\lambda X.t$, must $t$ have a function type, not a non-function type?

In Section 23.4 Examples, values of base types and of recursive types  are type abstraction values, because their definitions in the section are   functions by Church encodings.

Thanks.

Short Answer: In λX₁. λX₂. ... λXₙ. t it doesn't matter if t is not a function, but if so, it may not be an interesting example for introduction.

Long Answer:

First of all, technically speaking, the type system defined in Figure 23-1 does NOT have any base types such as Bool or Nat. A type of t in λX. t is either a type variable X, a function type T → T, or a universal type ∀X. T.

Section 23.4, however, takes Nat as an example. So let's consider an extended type system by adding some base types and its values, terms, typing rules, etc. like Section 11.1 does.

Then we can consider, for example, a term λX. 42. This is a well-typed term. Proof:

\[
  \cfrac{}{
  \cfrac{\mathrm{X} ⊢ \mathrm{42} : \mathrm{Nat}}{
  ∅ ⊢ \mathrm{λ X. 42} : \mathrm{∀ X. Nat}
  }}
\]

This term, however, is not very interesting; polymorphism doesn't play any important role here.

Also, we can consider a type ∀X. X. But there is no term of type ∀X. X (i.e. there is no inhabitant of ∀X. X). This can be proved through the Curry-Howard correspondence. But this example may not be suitable for introduction of System F.

Section 23.7 writes a bit more interesting example. If we extend the type system by adding errors, we can consider a term λX. error. This term doesn't throw an error during an evaluation because of the type-abstraction. This observation gives an idea of a new type erasure method, described in Section 23.7.


Why does this grammar derive into $\beta \alpha ^*$ instead of $\alpha ^* \beta$? In this video clip the teacher presents a grammar $A \rightarrow A \alpha | \beta$ and after providing the parse tree explains that the regular expression for the language generated is represented as $\beta \alpha ^*$.

Why isn't it $\alpha ^* \beta$ instead? Isn't the grammar left-recursive into terminal $\alpha$ and once terminal $\beta$ is reached the string ends?

Try some derivations:

$A\Rightarrow \beta$
$A\Rightarrow A\alpha\Rightarrow \beta \alpha$
$A\Rightarrow A\alpha\Rightarrow A\alpha\alpha\Rightarrow \beta \alpha\alpha$

The pattern is clear: starting from $A$, we'll generate strings of the form $\beta\alpha\dotsc\alpha$, in other words, $\beta\alpha^*$. Since at any stage we have $A$ on the left of the sentential form, we'll eventually generate strings with $\beta$ on the left.

If the grammar had been $A\rightarrow \alpha A\mid \beta$, then we'd derive strings of the form $\alpha^*\beta$.


Instantiating a class with a sig'd type in Coq I can easily define a class that corresponds to the notion of a "monoidal structure" on a type M via
Definition associative {X:Type} (f : X -> X -> X) : Prop := forall x y z:X, f (f x y) z = f x (f y z).

Definition opId {X:Type} (f : X -> X -> X) (e : X) : Prop := forall x:X, f e x = x /\ f x e = x.

Class Monoid (M:Type) :=
  { binM : M -> M -> M ; idM : M ; assocMProof : associative binM ; idMProof : opId binM idM }.

and then instantiate it, for instance, with the type of endomorphisms over a given type with operation being composition:
#[refine] Instance compMon {X:Type} : Monoid (X -> X) :=
{
binM f g := fun x => f (g x) ; idM := fun x => x
}.
Proof.
  - unfold associative. reflexivity.
  - unfold opId. intro. split. reflexivity. reflexivity.
Defined.

but how would I, for example, go about defining the monoidal structure on the set of injective endomorphisms over a type? (Or even better, formalizing the notion that binM in compMon restricts to such a monoidal structure?) I presume I would want to define injective and then instantiate Monoid {f : X -> X | injective f} but not only would that seem to entail defining a new binary operation (which takes functions f, g and proofs of injectivity i, j and produces a new function with a new proof of injectivity) and a new identity, it seems that said binary operation wouldn't even be associative (of course $f \circ (g \circ h) = (f \circ g) \circ h$ as functions, but the proofs of injectivity aren't the same?). What am I missing?

You are missing propositional extensionality. It is not provable in straight Coq but you can assume it. And while you are at it, if your going to do math, you will also want function extensionality. Both forms of extensionality follow from univalence, which is also an extensionality principle, except that this one is for the universe of types.
If you prefer to avoid all this you can go down the road of setoids: you equip every types with an equivalence relation that serves as the equality relation. You then have to keep proving that your functions preserve these relations. It's a lot of "fun".


Proving monad laws for flatMap and unit, given laws for compose and unit I'll use scala notation but hopefully things will make sense in general (I'm trying to prove that you can define a monad using either [flatMap (aka bind) and unit] or [compose and unit])

The book Functional Programming in Scala (github at https://github.com/fpinscala/fpinscala) makes the claim that if we have a type constructor M and functions compose and unit

compose(f: A => M[B], g: B => M[C]): A => M[C]
unit(a: A): M[A]

satisfying

compose(compose(f, g), h) == compose(f, compose(g, h))
compose(f, unit) == f
compose(unit, f) == f

then defining a function flatMap

flatMap(x: M[A])(f: A => M[B]) = compose(_: Unit => x, f)(())

will satisfy

flatMap(flatMap(x)(f))(g) == flatMap(x)(a => flatMap(f(a))(g)
flatMap(x)(unit) == x
flatMap(unit(y))(f) == f(y)

I can't prove this. The easiest place to see my confusion is trying to show the last identity. We have

flatMap(unit(y))(f) = compose(_: Unit => unit(y), f)(())

If there was some rule like

compose(_: Unit => unit(y), f)(()) = compose(unit, f)(y)

or more generally

compose(f∘g, h)(a) = compose(f, h)(g(a))

then we could conclude that the identity is true, but as is, I don't see any move I'm allowed to make. Any ideas?

The solutions for this question https://github.com/fpinscala/fpinscala/blob/master/answerkey/monads/10.answer.scala only do the case where compose is defined in terms of flatMap but the questions asks "Prove that these two statements of the identity laws are equivalent" so I think the solutions should include both implications.

That rule you are asking for is (with slight tweaking) a naturality condition mathematically. It would be more naturally written as: $$\mathtt{compose}(f\circ g,h)=\mathtt{compose}(f,h)\circ g$$
If compose used the typical order for composition, you could write it more prettily as: $$(h\odot f)\circ g = h\odot(f\circ g)$$
where $h\odot f = \mathtt{compose}(f,h)$.

The type A => M[B] corresponds to the hom-functor for the Kleisli category of $M$, $\mathcal{C}_M(A,B)\equiv\mathcal{C}(A,MB)$. Given a Kleisli arrow $h : B \to MC$, we have the function $h\odot- : \mathcal{C}(A,MB)\to\mathcal{C}(A,MC)$, and this is natural in $A$. The naturality diagram is:
$$\require{AMScd}
\begin{CD}
\mathcal{C}(A,MB)@>h\odot ->>\mathcal{C}(A,MC) \\
@V-\circ gVV @VV-\circ gV \\
\mathcal{C}(X,MB) @>>h\odot -> \mathcal{C}(X,MC)
\end{CD}$$
where $g : X \to A$. (In fact, this can also be read as a naturality diagram for $-\circ g : \mathcal{C}_M(A,-)\to\mathcal{C}_M(X,-)$.) That $h\odot -$ is natural can be easily derived from its definition as $f\mapsto \mu\circ Mh \circ f$ where $\mu$ is the multiplication of the monad $M$, i.e. flatten, and $Mf$ is the functorial action of $M$, i.e. map.

At any rate, the equation you want would be a free theorem if Scala was a suitably nicely behaved language. Indeed, that Scala isn't "suitably nicely behaved" is an omnipresent problem and leads to many of these laws not actually holding. (This problem occurs with Haskell too, but not nearly so catastrophically.) I assume Paul and Runar discuss this and free theorems somewhere in the book. They're certainly aware of it.


Caches and reading a PDF I am currently learning about caches in Systems class, and I had a few doubts about what exactly happens when a Computer reads a PDF. This is the sequence that happens in my mind:

The CPU checks if the pages of the PDF I want to read are there in cache.
It is not, so we keep going down the Cache hierarchy until we get to the Hard Drive, from where the PDF is located and read into main memory.
From main memory, it goes all the way back to L1 cache, and the CPU reads it.

Is there anything wrong with the simplification I have given above?

I know that Cache entries use the effective memory address of its data to determine where the data will be placed in the structure.  Here, in this example, what exactly will be the memory address of the PDF?

When a computer reads a PDF...
You can take several perspectives.

From Acrobat reader, it asks the operating system to read a file, copies it to memory then interprets drawing commands. From applications POV, caches don't exist.

Of course, there is nowadays a disk cache in RAM, where the last used sectors are kept for shorter access time. Some OS even trick the MMU between the disk cache and application address spaces so that data is not even copied. That cache is not visible to applications (which can also have their own caching, for example pre-rendered pages...)

From the operating system, CPU caches needs sometimes to be manually managed, on some platform, particularly when there are peripherals that are modifying memory without CPU intervention ("non coherent DMA"). It could be the disk controller reading that PDF file. On current high performance CPUs, the kind you find in computers or tablets where Acrobat can be installed, the CPUs practically manage their caches transparently.

So, CPU caches are mostly hidden to software.

Cache are made of two parts : the datas, and the tags.
Datas contains a portion of RAM area.
Tags indicate which part of the RAM is in the cache.
Data is grouped in chunks ("cache line"), usually 32 to 128 consecutive bytes.

When a CPU accesses its caches, it lasts usually less than 5 cycles for L1 caches, and less than 20 cycles for L2 caches.
Accesssing DRAM can waste hundreds of cycles.
Despite being very small (for example 32kB L1 compared to 4GB DRAM), they are incredibly efficient, because, in reality, accesses are often grouped, or consecutive, or repetititve, so that the same parts of main memory are accesses several times.


What does this context-free grammar generate? The grammar is

$$ S\to aSb\ |\ bSa\ |\ SS\ |\ \epsilon. $$

I think this generates the set of strings with equal numbers of $a$'s and $b$'s based on examples I've done. Is this correct?

You conjecture that your grammar generates the language $L$ of words having as many $a$s as $b$s. In order to prove your conjecture, you should do two things:

Prove that every word generated by the grammar belongs to $L$.
Prove that every word in $L$ can be generated by the grammar.

In this case, the first part is easy to prove by structural induction. The second part is more difficult, so here is a hint. Given any non-empty $w \in L$, show that it can be decomposed as either $w = xayb$ or $w = xbya$ for some $x,y \in L$. Given this lemma, you can use induction on $|w|$.

Here is a hint for the lemma. Let $d_k(w) = |\{i \in [k] : w_i = a\}| - |\{i \in [k] : w_i = b\}|$, and let $d(w) = d_0(w),d_1(w),\ldots,d_{|w|}(w)$. For example, $d(aabb) = 0,1,2,1,0$ and $d(baba) = 0,-1,0,-1,0$. A prefix $w_1\ldots w_k \in L$ corresponds to a position $k$ such that $d_k(w) = 0$.


When you do a remote desktop connect to another pc which pc's processing power do you have? Are you just accessing the data and things on the PC you are connecting to or, if it had a better processor/ram/etc, are you able to take advantage of that?

When you remote desktop into another computer you are actually using that computers hardware. You are not running a virtual machine of that computer, which would take your main computers resources.


Looping and branching with Algorithmic Differentiation Algorithmic (aka Automatic) Differentiation is a wonderful technique for numerical computation of derivatives. I understand how it relates to the fact that we know how to deal with every elementary operation in a computer program, but I am not sure to get how this applies to every computer program.

To quote from this wikipedia page:

  every computer program, no matter how complicated, executes a sequence of elementary arithmetic operations

.. which I totally agree with. However, it sounds then that the number $m$ of variables newly produced from any $n$ initial input is fixed and can be determined from static code analysis. But this is not straightforward to me since constructs like:

if x_1 > x_2:                         # branching
    perform 4 elementary operations
else:
    perform 84 elementary operations
endif

and:

while x_1 < x_2:                      # looping
    perform 2 elementary operations
endwhile

do exist in so-called « complicated » computer programs. This make the number (and the type) of elementary operations not straightforward to compute in advance. And I even suspect it is impossible to gess that in general, right?

Does AD support such branching and looping programs?
Are there extensions of AD adapted to programs that are not just intricate closed-form expressions?
How does AD deal with Turing-completeness?

AD supports arbitrary computer programs, including branches and loops, but with one caveat: the control flow of the program must not depend on the contents of variables whose derivatives are to be calculated (or variables depending on them).  Here is an example:

if x = 3 then 9 else x * x

At close inspection you will recognize that the above is really just an inefficient way of implementing $x*x$.  If you evaluate this program at $x = 3$, then the result is the constant $9$.  But the derivative of constants is zero, which is obviously not the right answer, which should be $6$.

The reason is that AD will typically only look at the executed branch of your program.  It is perfectly ok to have branches on conditions that don't involve numbers, or conditions involving number variables not part of the computational graph for derivative calculations.  It's also ok to look at fixed properties of derivative values (e.g. the dimension of a vector).  But as soon as you "look" at the contents of a variable that depends on one of the inputs to determine what calculation to perform next, you will "break the chain".  AD does basically just that: apply the chain rule.

Users of AD should view programs as "configuring" a fixed computational graph.  If running the program with different inputs for which derivatives are requested gives you different computational graphs, AD may not always give the correct result.


Construct a TM for $L = \{ M | M$ is a Turing machine with no useless states} I'm trying to construct a recursively enumerable TM for this language. (Useless state: one that is never entered during a computation on any input).

The TM L:
Write out all of M's states, generate input in lexicographical order one at a time, and after one is generated, simulate M on the input and mark down which states M has entered. If M enters all states, halt, if M halts without entering all states, generate the next input in lexicographical order and repeat the process. (Keeping the list of entered states between simulations, since once a state is entered for any input, it is not considered useless).

My question is, what happens if M does not halt on input $w_i$ but will halt and in fact enter all states on $w_{i+1}$?
Then L will get stuck in an infinite loop on $w_i$ and not realize that M's behavior on $w_{i+1}$ means L should actually accept--thus L will not eventually halt and accept.

Is there a way to deal with this problem or is this TM just not the right way to show this language is recursively enumerable?

You need dovetailing. This is quite common in such problems.

As you pointed out, we can not simply run $M$ on an input $w$, since that might diverge. To avoid that, we enumerate all the possible pairs $(w,k)$ where $w$ is an input word, and $k$ is a natural. For each such pair, we run $M$ on input $w$ for at most $k$ steps. This will never diverge because $k$ bounds the computation. If $M$ within that bound visits all states, we accept. Otherwise, we try the next pair.

Note that, in order to enumerate all such pairs, we need a computable bijection $(\mathbb N\times \mathbb N) \to \mathbb N$ (or, equivalently, $(\Sigma^*\times \mathbb N) \to \mathbb N$). The existence of such a dovetailing function is one of the standard computability results.


Basic question about backjumping in SAT solvers I am reading "Formalization and Implementation of Modern SAT Solvers", by Filip Marić.

My question is about how backjumping is defined. In an example [1], there is a conflict clause C equal to

[-1,-2,-3]

that has already been explained and learned. The decision trail is

|6, 1, 2, |7, |3, 4, 5,

where true decisions are marked with | and the others are propagated literals.

Then the algorithm performs a backjump to the level of literal 2, the most recently asserted literal that makes the conflict clause a unit clause.
This modifies the decision trail to

|6, 1, 2

and immediately propagates -3 since [-1,-2,-3] is unit now, obtaining

|6, 1, 2, -3

What I would like to understand is: why not define backjumping so that the choice of 7, and all the (potential) work performed after it, were preserved? In this example, choosing 7 didn't do much, but it could have done a lot of propagation that we would not want to waste. There could also be other choices between 7 and -3 that we would benefit from preserving. It seems to me that the algorithm would be perfectly correct if it has backjumped to a decision trail

|6, 1, 2, |7, (any other choices not involved in the conflict, and literals propagated from 7 and them)

and then propagated -3 and got

|6, 1, 2, |7, (any other choices not involved in the conflict, and literals propagated from 7 and them), -3.

More generally, I am proposing that backjumping be defined not to go back to the most recent literal in C making it a unit clause (that is, 2), but to the most recent literal in the trail immediately before the last literal (-3) in C. That would be whatever is immediately before -3 in the trail, before the backjump, including 7, its propagations, and whatever other non-conflicting choices that happen to have been made.

Am I correct that this would be a better alternative that preserves work, or am I missing something?

[1] Fig. 6, trace of Example 7 if you are curious, but there is no need to go look as I think all the relevant information is here.

The intervening assignments between the current assignment and the backjump point might have been arrived at via considerable backtracking and backjumping themselves and it would be wasteful to repeat all that work.  But in the context of a modern solver that work may not need to be repeated, because:

Any conflicts that occurred during the intervening assignments should have produced conflict clauses that rule out those time-wasting bad assignments in the immediate future.
Some solvers implement "phase saving" which remembers whether a variable was assigned true or false across backjumps (and restarts).  So when DPLL chooses that variable again as a decision variable it will use the same true/false value, essentially picking up where it left off before the backjump.
The intervening assignments may not be repeated in the same order after the backjump.  Solvers have heuristics that decide which variable becomes the next decision variable.  These heuristics usually give preference to variables recently involved in conflicts, which usually has the effect of shuffling the decision variable order after every conflict.

There is another reason to backjump past 7 and then assert -3 and that is because of the way two-watched-literals works.  Two-watched-literals is a clever algorithm for noticing when clauses are made unit by an assignment.  It uses a lazy data structure that does not need to be updated for every clause referenced by an assignment and more importantly does not need to be updated at all when backtracking or backjumping.  You can assume every SAT solver that implements DPLL also uses this algorithm to track unit clauses.

But in order for the lazy data structure to work there are procedural rules that must be followed.  One of them is that you must roll back decision variable assignments and their unit propagations as a group.  So to use your example, if -3 were asserted after the 7 assignment instead of before it and the 7 assignment were ever rolled back, then the -3 assignment would be undone separate from the |6 1 2 assignments that caused it.  This would leave clause C, [-1 -2 -3], as a unit clause but two-watched-literals would not detect it.  DPLL search is now broken and the solver may be confused enough to later claim that it has a satisfying assignment when it doesn't.  If -3 is asserted together with the other consequences of the 6 assignment, then all the implications of that assignment will be rolled back together as they must be.


If NP is not a proper subset of coNP, why does NP not equal coNP? I am studying some lecture notes on the complexity of algorithms.
The notes give a proof that NP is not a proper subset of coNP.
However, they still assert that NP is a subset of coNP (which I agree with).
So, in this case, why does it not follow that NP is equal to coNP?

$\{2,3\}$ is not a proper subset of $\{3,4\}$, yet the two clearly are not equal.

Comparing sets is not like comparing numbers: two sets might not be comparable.

Additionally, NP is not a subset of coNP, or at least, it is not known that this is the case. You are either misreading the textbook, or your textbook is wrong, since proving that $NP \subseteq coNP$ would be a massive result.

$P\subseteq coNP$, perhaps that is what you actually read?


Average Case Analysis for finding max in array with duplicated element I've read some posts about counting the number of assignment inside code of finding the maximum value in array like this:

FindMax(L):
   n = len(L)
   max = L[1]
   for i = 2..n:
      if (max < L[i])
          max = L[i] (**)
   return max

According to this post and post, it's about the array that elements are strictly distinguish. So if the array contains values may be duplicated (for example, elements are integer in range [1, m], m = 3, with any length of array), how could we calculate the number of (**) will be executed in average case?

Let us consider the following distribution: each array element is chosen independently and uniformly from $\{1,\ldots,m\}$. Let us denote by $I_i$ the indicator variable for the event that ( ** ) gets executed for the $i$th element (so $I_i = 1$ if ( ** ) gets executed, and $I_i = 0$ otherwise). Linearity of expectation shows that the expected number of times that (**) gets executed is $$ \sum_{i=2}^n \Pr[I_i]. $$
(This uses the fact that $\mathbb{E}[I_i] = \Pr[I_i]$.)

It remains to compute the probability of $I_i$. If $A[i] = j$ then (**) happens iff $A[1],\ldots,A[i-1] \in \{1,\ldots,j-1\}$, which happens with probability $\bigl(\tfrac{j-1}{m}\bigr)^{i-1}$. Therefore
$$
\Pr[I_i] = \sum_{j=2}^m \frac{1}{m} \left(\frac{j-1}{m}\right)^{i-1}.
$$
In total, we get
$$
\sum_{i=2}^n \Pr[I_i] = \sum_{j=2}^m \frac{1}{m} \sum_{i=2}^n \left(\frac{j-1}{m}\right)^{i-1}.
$$
You take it from here.


Algorithm which finds the maxmal solution that satisfies the following constraints I have $a_1, a_2,\dots,a_n$ and $b_1,b_2,\dots,b_n$ and an upper bound $U$ and $n$ linear equations of the form:

$k_1 * a_1 + b_1 = x$

$k_2 * a_2 + b_2 = x$

$\dots$

$k_n * a_n + b_n = x$

Additional info where $r \in \{ 1,2,\dots , n \}$:

$a_r$ is prime
$0 \leq b_r < a_r $
$k_r b_r, U, n, \in N_0$ and $(a_r\in N)$

I'm looking for an algorithm that computes the largest $x$ which satisfies all of the given equations such that for the given upper bound $U$ the additional constraint $x \leq U$ holds. If there is no such $x$ a simple "no solution" as output is fine.

First Example:

Given data:
$a_1 = 3, a_2 = 5$ and $b_1 = 1, b_2 = 2$ and $U = 20$

The $n$ equations with substituted values:

$k_1 * 3 + 1 = x$

$k_2 * 5 + 2 = x$

The solution (largest $x$ which satisfies the equations and is $\leq U$ is 7 (set $k_1 = 2$ and $k_2=1$)

Second Example:

Given data:
$a_1 = 11, a_2 = 17$ and $b_1 = 1, b_2 = 2$ and $U = 20$

The $n$ equations with substituted values:

$k_1 * 11 + 1 = x$

$k_2 * 17 + 2 = x$

The solution (largest $x$ which satisfies the equations and is $\leq U$ is "no soluton" (there is no way to set $k_1$ and $k_2$ such that the equations are equal)

I'm struggling to come up with an algorithm which solves this efficiently. Currently my best approach is to compute all values of x which satisfy the first equation, then I compute all values of $x$ which satisfy the second equation and so on until I have $n$ sets, set $i$ represents the values of $x$ which satisfy equation $i$. Then I simply intersect all of them, if the result is an empty set then I output "no solution" otherwise I output the max element of the resulting set. This approach is very inefficient :/

What do you think about my approach how could I compute the largest x which satisfies all of the constraints above more efficiently?

Note: the reason I know that there is a more efficient solution is because I have encountered this problem during a programming competition. I'm expecting that the solution will use elementary number theory since prime numbers are involved. I just don't know how else to approach this.

You want a solution $x$ such that

$$x \equiv b_i \pmod{a_i}$$

for all $i$.  By the Chinese remainder theorem, this is either impossible or it is equivalent to

$$x \equiv b \pmod{a}$$

where $a = \text{lcm}(a_1,\dots,a_n)$ and $b$ can be computed using the Chinese remainder theorem.  In other words, the solutions are all of the form $b$, $b+a$, $b+2a$, $b+3a$, etc.  From there it is easy to find the largest solution $x$ such that $x\le U$.


Why in the code i ≃ n? i=2;
while(i<n)
{
   write('*');
   i=i*i;
}

Why $n ≃ i$?

I mean suppose $n=1000$ and so $i= 2,4,16,32,256,65536$ is in every steps.

In the book wrote $2^2 power(k)$ is pattern for growing $i$ so  $n ≃ i$ and...

Now 65536 or 256 isn't equal to 1000 or around 1000.

But why  $n ≃ i$?

This chapter is about notations.

The symbol $\space ≃ \space$ means "asymptotically equal to".

So when you read $ n ≃ i$, you can read it as $n$ asymptotically approaches $i$.

This means that the more $n$ increase in size, the more $i$ increase in size but $n$ never become equal to $i$.

  I mean suppose $n=1000$ and so $i=2,4,16,32,256,65536$ is in every steps.

This contains an error: when the program start $i=2$. At the first cicle, $i=2^2 = 4 $. $\space$ At the second cicle, $i=4^2=16$. $\space$ At the third cicle, $i = 16^2= 256$. $\space$ At the fourth cycle, $i=256^2 = 65536$. $\space$ At the fifth cycle the program stops since $i>n$.


Build a histogram from a very large data sample I want to calculate a histogram from an array of size N. N is very large.

I know 2 ways to do so:

The naive approach is to find the maximum and the minimum in the first traverse and to split the range into equal bin ranges then to fill bins during the second traverse. However this approach produces degenerate histograms where most of data is piled in one bin if the sample has outliers.
The way to counter degenerate histograms is to calculate IRQ or MAD, then calculate range based on this robust measure of scale, and then fill bins in one traverse. However calculation of IRQ or MAD may be slow and requires random access to the array.

I'm intrested if there is a way to build a histogram in between this extreme approaches fulfilling conditions:

some loss of quality is acceptable
the array doesn't fit in RAM so random access is the thing I want to avoid
low time complexity, i'm ready to trade space ~log(N) for time

One reasonable method is to choose a random sample of, say, 1000 items from the array.  This can be done in a single pass (say, using reservoir sampling) or using random access (but here we need only 1000 random accesses, so this is probably faster than a single linear pass through the data).

Compute a histogram of those 1000 items, and use that to select bin ranges.

Then, perform a second linear pass on the entire dataset where you accumulate counts in those bins, using those bin ranges.

This will be efficient (nearly as efficient as the naive approach), and help you avoid degenerate histograms.

There are more sophisticated methods that are possible as well, from the literatures on streaming algorithms.  For instance, you can use a streaming algorithm to estimate the quantiles of the data, which lets you estimate the IQR in a single pass through the data, then you use these estimated information to choose bin boundaries, then perform a second linear pass where you accumulate counts in those bins.    There are also streaming algorithms to estimate the histogram counts, then you can use that to choose bin boundaries, then perform a second linear pass where you accumulate counts in those bins.  There's a beautiful literature on this subject.  See, e.g., Tracking Quantiles of Network Data Streams with Dynamic Operations by Cao et al, Approximate Frequency Counts over Data Streams by Manku et al, and many others.  That said, while this is principled and elegant, it might also be more complex than necessary -- simple random sampling might be good enough for your needs.


How to find the spot which is furthest away? Last night I thought about the following problem:

Given any map (for example from Germany), how to find the spot which is furthest away (in every direction) from the nearest (any) town/village?

I thought about how one would proceed to figure out in which problem class this problem belongs to and how to prove that.
And also how to determine which would be an efficient algorithm for this problem.
Basically I would like to learn about the steps how a professional in complexity theory would start to work on a problem like this.

I read on Wikipedia about the Nearest neighbor search which I think come close to what I'm looking for. But I wasn't able to find something like "furthest neighbor search".

As you get further from Germany, you will get points which are farther and farther away. So unless you are taking into account the spherical nature of Earth, we need to change the problem, and look for a location in Germany which is farthest away from all villages in Germany. This is known as the largest empty circle problem, and can be solved essentially by computing the Voronoi diagram of the set of villages in Germany.


HamiltonianCycles in Random Graphs Lets say we consider the Erdős-Renyi undirected random graph $G(n,p)$ with $V(G) = \{1,2,\cdots,n\}$ and $\displaystyle{P((u,v)\in E(G)) = p} \quad \forall u,v \in V $.

Is there anything we can say about the probability of the $G$ containing a $HAM$ Cycle?

This seems like a helpful quantity to figure out for certain computations

Generating random graphs and seeing what fraction contains a $HAM$ cycle can of-course be done.

What is the rate of increase of $P(G\text{ contains }HAMCYC)$ as $p$ increases?

The classical version of this question is for Hamiltonian cycles, but there is probably little difference. I will only consider the version with cycles.

In order for a graph to contain a Hamiltonian cycle, the minimal degree should be at least 2. This is essentially the only obstruction for Hamiltonicity. To state this we need to define the following process:

For every pair $\{x,y\} \in [n]$, let $\theta_{xy} \sim U([0,1])$ (independently).
Define $G_p = \{ \{x,y\} : \theta_{xy} \leq p \}$.

By construction, $G_p \sim G(n,p)$. As $p$ goes from 0 to 1, more and more edges are "exposed". Bollobás proved the following result:

  Let $p_2$ be the minimum $p$ such that the minimal degree of $G_p$ is at least 2.

  Let $p_H$ be the minimum $p$ such that $G_p$ is Hamiltonian.

  With high probability, $p_2 = p_H$.

The expected degree of a vertex is $p(n-1) \approx pn$. This suggests looking at $p = c/n$. A simple calculation shows that for appropriate values of $c$, the degree of a vertex has distribution roughly Poisson with expectation $c$. In particular, the probability that a vertex has degree less than 2 is roughly $q = e^{-c}(1 + c)$. A further calculation shows that these events for different vertices are roughly independent, and so the distribution of the number of vertices of degree less than 2 is roughly Poisson with expectation $nq$. In particular, the probability that the minimal degree is at least 2 is roughly $e^{-nq}$, for appropriate values of $c$. If $c = \log n + \log \log n + r$ then $q = \frac{\log n + \log \log n + r + 1}{e^rn\log n} \approx \frac{e^{-r}}{n}$, and so $e^{-nq} \approx e^{-e^{-r}}$. This suggests the following result:

  The probability that $G(n,p)$ is Hamiltonian for $p = \frac{\log n + \log\log n + r}{n}$ tends to $e^{-e^{-r}}$ for constant $r$.

  If $r \to -\infty$ the probability tends to zero, and if $r \to \infty$ it tends to one.

This result indeed holds.

You can see a final project of Brunet for some pointers. For more information, consult any decent textbook on random graphs; Hamiltonicity is a classical topic which would be covered in many of them.


Given $T(n) = \sum_{i = 0}^{\log n} i 2^i$, what is $O(T(n))$? I'm trying to perform an asymptotic analysis on a function:

$T(n) = \sum_{i = 0}^{\log n} i 2^i$

The above expression came about when I began with:

$T(n) = \sum_{i = 0}^{\log n} 2^i \log (2^i)$

Is there a tight, closed-form expression for $O(T(n))$?

There are two ways to calculate the sum. The first way is to write it as $$\sum_{i=1}^{\log n} \sum_{k=1}^{i}2^{i}.$$

You change the order of sum and the calculation is the sum of geometric series.

Another way is to write it as $f(x)=\sum_{i=1}^{\log n} x^{i}$, and find the $xf`(x)|_{x=2}$, again a sum of geometric series.


Does a collision occur if two packets are sent at the same time in Slotted AHOLA? There's something I don't really understand about the Slotted AHOLA protocol, and I hope you can help me: what happens if a station wants to send two packets at the same time? Will it be considered as a collision? If not, when will the first and second package be sent?

I did some research here but all I found was probability formulas that I haven't seen yet...

A station is not allowed to send two packets at the same time.  Each station is only allowed to send one packet at a time.  If the station has multiple packets it wants to send, it can start sending one of them but it must queue the others and wait to send them later.

The protocol does not impose any requirements on how long a station must wait to send the other packets.  Suppose Alice has two packets to send.  Alice is required wait to send the second packet until some later point after she has finished sending the first packet.  Beyond that, it's up to her exactly when he tries to send it.  The protocol doesn't specify anything in particular.   Some stations might try to send the second packet immediately after they finish sending the first packet.  Other stations might wait a while (for whatever reason) in between.  There are no guarantees and no requirements.


Designing a scheduling algorithm I have only intro CS under my belt, so I'm looking for some fast advice. I want to write a scheduling algorithm for the following scenario.

I have customers who have selected how many hours they want and what times they are available (choosing in 4 hour increments). I have 1 service person I then need to schedule to maximize the number of hours scheduled (so only 1 service person at a time). There is no ranking of preferences by customers, just a binary availability for each time slot and a number of hours. My thought was to start with the biggest job, schedule that, and then work downwards greedy-style. I also thought this must be a well-known problem. Can someone tell me the name of this 'problem' or what else I should be looking at? I can also restructure the inputs if that would help finesse this into an optimized algorithm that exists out there.

Since a customer must either be assigned all the requested hours or none at all, this problem is $NP$-complete. This can be seen by reduction from Exact Cover.

A polynomial algorithm is unlikely to exist. Starting with biggest job first might be a reasonable heuristic for many cases, but there are no performance guarantees.


Prove simple theorems in Haskell in automated way I would like to prove in Haskell, whether in vanilla Haskell or using some libraries / tools, some simple theorems such as:
and [n*(n+1)/2 == sum [0..n] | n <- [0..]]

Is there a simple enough (ie. fully automated) way to prove such theorems involving integers in Haskell? I am not really interested in the proof itself, or a counterexample, but merely a yes/no answer.
There's this publication which doesn't seem practically usable; other than that most of everything else seems to be rather complex, ie. involving a completely separate language and not concerning Haskell.

Look at Agda [1][2]
I think that it's exactly what you are looking for.
I recommend using its emacs mode for autocompletion and hole/interactive programming. [2]/quick-guide.html
A very good introduction is plfa [3], also [2]/tutorial-list.html
[1] https://en.wikipedia.org/wiki/Agda_(programming_language)
[2] https://agda.readthedocs.io/en/v2.6.0.1/getting-started/what-is-agda.html
[3] https://plfa.github.io/


Minimum s-t cut in weighted directed acyclic graphs with possibly negative weights I ran into the following problem:

Given a directed acyclic graph with real-valued edge weights, and two vertices s and t, compute the minimum s-t cut.

For general graphs this is NP-hard, since one can trivially reduce max-cut to it by simply reversing the edge weights (correct me if I'm wrong).

What is the situation with DAGs? Can min-cut (or max-cut) be solved in polynomial time? Is it NP-hard and, if so, are there any known approximation algorithms?

I tried to find work on this but wasn't able to (maybe I'm just using wrong keywords in my searches), so I was hoping somebody may know (or find) something about this.

You've refined your problem some more in the comments. To be more specific, you have a DAG with all edges flowing away from the source $s$ and towards the sink $t$ (that is, all edges are on a path from $s$ to $t$). You want to find the minimum cut between two pieces of the DAG, where the first piece is connected to $s$, and the second connected to $t$. For this problem, a variation of the standard linear-programming algorithm for MIN-CUT works, even with negative edge weights.

We use the same notation as in Wikipedia. The cost of edge $(i,j)$ is $c_{ij}$. We put a potential function $p_i$ on each node, and let $d_{ij} = p_i - p_j$. The LP is
$$ \begin{align*} \mathrm{minimize\ } & \sum_{(i,j) \in E} c_{ij} d_{ij} \\
\mathrm{subject\ to\ } & \ \ \ d_{ij} = p_i - p_j \ \ \forall (i,j) \in E \\ &\ \ \ d_{ij}  \geq 0 \ \ \ \ \ \ \ \ \ \ \ \, \forall (i,j) \in E \\ & \ \ \  p_s\, = 1 \\ & \ \ \ p_t \, = 0  \end{align*} $$

These equations guarantee that $0 \leq p_i \leq 1$, since every vertex is on some $s$–$t$ path. Similarly, since $d_{ij} = p_i - p_j$ is non-negative, the potentials on any path from $s$ to $t$ are decreasing. We still need to show that there is an optimal solution to the LP with all $p_i$ either $0$ or $1$. This follows from the fact that the value to a solution of the LP above is the expected value of the cut $C_w$, where $w$ is chosen randomly in $[0,1]$, and where cut $C_w$ is obtained by putting all vertices $i$ with $p_i\geq w$ in the first set of vertices, and all vertices  with $p_i < w$ in the second set.


Lambda Calculus Reduction I am a little confused to reduce these lambda calculus expressions.  I am instructed to give applicative and normal order reductions for these expressions.

$(a):$  $$(\lambda x. (\,(\lambda y.(* 2 y)\,) (+ x y)\,)\,)\,y $$

$(b):$  $$(\lambda  x. \lambda y. (x y)\,) \,(λz. (z y)\,)\,$$

Here are the steps I took in my first attempt at $(a)$:

$$(\lambda x. (* 2 (+ x y)))y $$
$$(\lambda x. (* 2 (+ x z)))y \thinspace $$

(substituting $y$ with $z$)
$$(* 2 (+ y z))$$

I'm unsure if I even reduced that correctly and how I would reduce in applicative order.
Any help is appreciated, thanks!

Applicative order: The leftmost, innermost redex is always reduced first.

Normal order: The leftmost, outermost redex is always reduced first.

Applicative order: $(λx.((λy.(∗2y))(+xy)))y$, the leftmost innermost redex is $(λy.(∗2y))(+xy)$. It is reduced first. Then we get $(λx.(∗2(+xy)))y$. Here $y$ is a free variable, renaming is not needed. Then the result is $(∗2(+yy))$.

Normal order:  $(λx.((λy.(∗2y))(+xy)))y \rightarrow ((λy.(∗2y))(+yy)) \rightarrow *2(+yy)$.
Applicative order: $$\begin{align*}(λx.λy.(xy))(λz.(zy)) &\rightarrow_\alpha (λx.λw.(xw))(λz.(zy))\\ &\rightarrow_{\phantom{\alpha}} λw.((λz.(zy))w) \\ &\rightarrow_{\phantom{\alpha}} λw.wy\end{align*}$$
The first $y$ is bound, the second $y$ is free. When $x$ is substituted by $(λz.(zy))$, name capture occurs, so the bound y is renamed by $w$.

Normal order reduction is same as the applicative order.


Two Step Verification. 4 digits vs 6 digits From a security level standpoint (such as Server, DataBase, Token Code, Authorization, Authentication, etc.) in regarding the Two Step Verification, usually Apple send a total of 4 digits security code vs Google send a total of 6 digits security code. What are the main differences?

The number of digits in such a one-time password is determined by the acceptable risk that an attacker who doesn't receive the verification code will be able to guess it (lucky guess). This risk takes into account several factors:

the probability that an attacker will be able to guess;
the negative consequences of an correct guess by an attacker;
the probability and the negative consequences if the code is too long and this discourages the user to use the service.

For an $n$-digit code, if there is a single valid code and the code is generated at random, then the probability of a lucky guess is $10^{-n}$. That's 1/10,000 for a 4-digit code, 1/1,000,000 for a 6-digit code. These are usually acceptable figures when the one-time code is a second factor (usually complemented by knowing a static password or possessing a physical device); they would be grossly insufficient if the code alone was enough to access a service.

When the code is sent from a remote server to the user's device, there is generally a single valid code which is randomly generated. Some one-time password schemes don't require communication between the server and the user's device, but instead have both sides generate a pseudo-random code in the same way using a shared secret key and a counter. In this case, there are usually several valid codes, to allow for desynchronization between the client and the server; this requires a slightly longer code to compensate for the increased number of possible lucky guesses.


Problem in finding the floating point representation? So, i was trying:

$(-10.75)_{10}$ and to convert it into 32 bit binary floating point representation.

i did this:
According to IEEE standard:  $(-1)^{-s} * 1.M * 2^{E-bias} $

 sign bit= 1 bit
 exponent= 8 bits
 mantissa= 23 bits

bias= $2^{n-1}-1 = 127$

  - 10   . 75
  ⇓  ⇓      ⇓
= 1 1010 . 11
= 1 1.01011 x 2^-3
= 1 1.01011 x 2^(124-127)
= 1 01111100 0101100 0000 0000 0000 0000   = 32 bits
  ⇓ ________ ____________________________
  ⇓    ⇓                  ⇓
 sign  Exponent         Mantissa

But the answer presented is:

  - 10   . 75
  ⇓  ⇓      ⇓
= 1 1010 . 11
= 1 1.101011 x 2^-4
      -------> why this happened, and why is 1 before '.'
= 1 1.101011 x 2^(123-127)
= 1 01111011 1010110 0000 0000 0000 0000   = 32 bits
  ⇓ ________ ____________________________
  ⇓    ⇓                  ⇓
 sign  Exponent         Mantissa

If i am wrong, where is it and please explain why..
Any help is appreciated.

Both answers seem wrong to me. A quick conversion in C++:

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <stdint.h>

int main (void)
{
    float x = -10.75;
    uint32_t* p = (uint32_t*)&x;
    printf("%x\n",*p);

    return 0;
}

Gives the output: c12c0000

Which is 1 10000010 010110000…

Your mantissa calculation is the correct one, but the binary exponent is +3, not -3 (that is, your number is greater than 1, not less than 1). In bias-127, that exponent becomes 130 (decimal).


Neural Network weight selection using Genetic Algorithm Hi I want to ask about weight selection in neural network using genetic algorithm.

Right now what I understand is

Initialize population
Encode the weight of the neural network to the chromosome
Calculating the error and fitness
crossover and mutation
looping until satisfy the condition

Is it the right thing?

if yes what I'm still not sure are :

If I have 50 chromosome in one population that means I must create 50 neural network?
Let's say I have 100 different input and I want the network to learn it by using weight selection only (not using backpropagation) and how I calculate the error? Testing and calculating the error of every input(using MSE) and divide it by 100?

I think that's all for now

Thank you

Your understanding is correct.

Yes, you do create a new neural network for each chromosome (although you're considering the network structure as fixed, so technically you could reuse them by just resetting the weights anew for each chromosome.
For the error, you're on the right track. For a GA, generally only relative differences in fitness are important, so it doesn't really matter if you divide by 100 or not -- that's just linearly scaling the fitness values. That might matter for some choices of genetic operators (e.g., roulette-wheel selection can be sensitive to absolute fitness values), but often it won't matter at all.


Can a CFG end have a non-terminal symbol in the middle of it? What is the correct way to write a CFG?

A -> B C' E
C' -> C
C' -> null

or

A -> B C'
C' -> C E
C' -> E

Both of those are valid context-free grammars. (For the same language.) The requirement for a context-free grammar is just that the left side of the production must have exactly one non-terminal, which both of them satisfy. (Usually, to make this more clear, we'd have a convention like non-terminals are uppercase and variables are lower-case, and we'd specify the start symbol. But it looks clear that you have $A$ and $C'$ as nonterminals and the rest terminals, with $A$ being the start symbol.)


Proving that a property is k-inductive with an SMT solver (parametric resettable counter) I'm following the slides at https://homepage.cs.uiowa.edu/~tinelli/talks/FT-11.pdf where Tinelli explains how k-induction works in the context of SMT based model checking.

A parametric and resettable counter is given as a Kripke structure by the following formulas:

Variables:

$x := (c, n, r, n_0)$, where:

$n_0$ is a positive integer (input)
$r$ is a boolean (input)
$c$, $n$ are integers (internal variables)

Initialization:

$I[x] := (c = 1) \wedge (n = n_0)$

Transitions:

$\begin{align*}
 T[x,x'] := (n' = n) & \wedge (& (r' \vee (c=n)) & \to (c' = 1)) \\
                     & \wedge (& \neg(r' \vee (c=n)) & \to (c' = c + 1)) \\
\end{align*}$

Property to prove invariant:

$P[x] := c \le n + 1$

Tinelli uses the following notation:

$I^i:=I[x^{(i)}],P^i:=P[x^{(i)}],T^i:=T[x^{(i−1)},x^{(i)}]$.

He then claims on page 52/90 that the formula $P := c \le n+1$ is an invariant of this system because $P$ is 1-inductive (while incidentally not being 0-inductive). If I'm following correctly, this means that $I^0 \models P^0$ and $I^0 \wedge T^1 \models P^1$ (base case) and $P^0 \wedge P^1 \wedge T^1 \wedge T^2 \models P^2$ (inductive step). In particular it means that the formula $P^0 \wedge P^1 \wedge T^1 \wedge T^2 \wedge \neg (P^2)$ is UNSAT. However, after playing a little with Z3Py I was able to find the following model for this formula and a corresponding representation of a state transition trace with $(c,n,r)$:

$c^0 = -1, n^0 = 0, c^1 = 1, n^1 = 0, r^1 = \text{True},c^2 = 2, n^2 = 0, r^2 = \text{False}$
$(-1, 0, *) \to (1, 0, \text{True}) \to (2, 0, \text{False})$

Intuitively this makes sense. The constraint on $n_0$ being a positive integer affects the base case formula $I^0$ but not the inductive step, and therefore the above model is a valid model of the induction formula for $i=1$ which means the implication fails.

Of course $P$ is an invariant of this system, but it would seem to me that we cannot show it with k-induction for k = 1.

What is the gap in my understanding of this material?

I don't see any gap in your understanding.  What you wrote looks correct to me.

Perhaps the author meant to use the property $P := c \le n+1 \land n \ge 1$.  I think with that modification, $P$ becomes 1-inductive but not 0-inductive.  I suspect the author was looking for a simple example of a property that is 1-inductive but not 0-inductive, and missed a small detail.

Good job catching this!


Calculating the runtime for a recursive algorithm If the runtime of a recursive algorithm could be expressed as

$T(n) = \begin{cases}O(1) & n \leq c \\ k * T\left(\frac{n}{k}\right) + \left(k + n * k \right)\end{cases}$

what would be the result of the asymptotic analysis (the Landau class)? $k \in \mathbb{N}, k \neq 0 $ is a constant value.

I would say that $k$ even if it is larger than $n$ is still a constant and therefore $T(n) = O(1) * T\left(\frac{n}{k}\right) + O(n) = T\left(\frac{n}{k}\right) * n $ for $n > c$.

So I would say that the algorithm is $O(n * log_k(n))$. Is this right? How could I prove this (formally correct)?

I have two main problems with this algorithm:

1) What is the runtime of $f(n) = (k + n * k)$? Can the $k$ be ignored so the runtime is $O(n)$?

2) I would like to use the Master theorem. I could see $T(n)$ in the form $a \cdot T\left(\frac{n}{b}\right) + f(n)$ with $a = b = k$. But then I need to check if $f(n)$ is $\in O(log_b a) = O(log_1 1) = ?$ This logarithmus is undefined, so can't I use the Master theorem?

1) $f(n) \in O(n)$, since $k$ is a constant.

2) If $a=b=k$, then $\log_b a = \log_k k$. Your specific case of $\log_1 1$ only appears for $k=1$. And if we insert $k=1$ into the original recurrence we get $T(n) = T(n) + n + 1$, which does not make much sense as a description of a runtime. So it is sensible to simply exclude this case.


Fitness model for scale free networks In order to generate scale-free networks, we can use this algorithm, derived from Barabási–Albert model:

1) we assign every node a "weight" $\theta_i$ (or two in the direct case).

2) we place $m$ edges between nodes by choosing the ends of the edges with probabilities proportional to the weights.

With the right choice of the coefficients $\{\theta\}$ we can generate a graph with the desired power-law distribution. A very popular method is the so-called Chung-Lu Model and it's, for example, used in the power.law.game function in the igraph library.
This model prescribes to number the nodes from 1 to N and then assign to each node a $\theta_i = i^{-\alpha}$, with $\alpha \in [0,1)$,  then select nodes as the ends of an edge with probability $p_{ij} \propto \theta_i \theta_j$, and repeating for all the edges to put in. The resulting graph will have a degree distribution $p(k) \propto k^{-\gamma}$, with $\gamma = \frac{\alpha}{\alpha +1}$.

My question is: why can't we simply consider a power-law distribution with a finite extent  $p(x) =  \frac{1-\gamma}{x_{max}^{1-\gamma} - x_{min}^{1-\gamma}} x^{-\gamma}$, then sample our $\theta_i$ from this distribution? This is more intuitive from my perspective, because if my expected degrees follow a power-law distribution, I expect that the graph degree distribution follows the same power-law.

I don't know if my solution is correct, but after some searching, I eventually came up to this conclusion:

The algorithm that is used to build the graph is not compatible with a different choice other than $\theta_i = i^{-\alpha}$.

This is because the algo is derived from the  Barabási–Albert with some modifies. We start with N nodes, and we add a link between a couple of nodes every time step until we have added $mN$ edges. First we normalized the weights so they will be the probability that we choose the node $i, \;$  $\sum_{i=1}^{N} i^{-\alpha} \sim \frac{1-\alpha}{N^{1-\alpha}}$. We can easily compute the rate at which the node acquires links, since it will be proportional to its degree:
\begin{equation}
\frac{d\,k_i}{dt} = \frac{k_i}{2mN} =  \frac{1-\alpha}{N^{1-\alpha} i^\alpha},
\end{equation}
this means that we will select the node $i$ with probability $p(i) = k_i ^{-\frac{1}{\alpha}}$. This is equal to the probability that a node has a degree $k>k_i$, so it is related to the cumulative probability distribution:
\begin{equation}
P(k>\bar{k}) \sim k^{-\frac{1}{\alpha}} \rightarrow p(k) \sim k^{-\frac{1}{\alpha} -1} \equiv k^{-\gamma},
\end{equation}
where $\gamma = \frac{1+\alpha}{\alpha}$.
Is this a good answer?


Could quantum computing eventually be used to make modern day hashing trivial to break? Simply put, if one were to build a quantum computing device with the power of, say, 20 qubits,  could such a computer be used to make any kind of modern hashing algorithm useless?

Would it even be possible to harness the power of quantum computing in a traditional computing application?

Quantum computers might have some advantage over classical computers for some cases. The most remarkable example is Shor's Algorithm which can factor a large number in polynomial time (while classically, the best known algorithm takes exponential time). This completely breaks schemes like RSA, based on the hardness of factorization.

This is not necessarily the case for hash functions. First, we need to define what it means to break a hash function. One way to break it is called pre-image attack: you give me hash value $v$, and I need to find a message $m$ such that $\operatorname{hash}(m)=v$. Another attack is the collision attack, in which you give me nothing, and I need to come up with two different messages $m_1, m_2$ that have the same hash $\operatorname{hash}(m_1)=\operatorname{hash}(m_2)$. This is easier than finding a preimage, since I'm not bound to the a specific $v$.

What can Quantum computers do? The main result is Grover's search algorithm: a method for a quantum computer to search in an unsorted database of size $N$ with time $O(\sqrt{N})$ (while classically it will take an expected time of $N/2$).

With Grover's algorithm, finding a preimage of a hash function whose output is $k$-bits  takes $O(2^{k/2})$ time, rather than $O(2^k)$.

Is this a problem? Not necessarily. Hash functions are designed such that time $2^{k/2}$ is considered "safe" (in other words, the hash designers always double $k$). This is due to the Birthday paradox with which finding a collision is possible with time $O(2^{k/2})$ by a classical computer.

The nice thing about Grover's algorithm that it is optimal - every other quantum-algorithm to find an element in an unsorted database will run in time $\Omega(\sqrt{N})$.

Can quantum-computers perform better collision attacks? Actually I'm not sure about it. Grover's algorithm can be extended, such that if there are $t$ items (that is, preimages), the time to find one is reduced to $O(\sqrt{N/t})$. But this gives no collision - running the algorithm again might return the same preimage. On the other hand, if we choose $m_1$ at random, and then use Grover's Algorithm, it is probable that it will return a different message. I'm not sure if this gives better attacks.

(this answers the more general question, without restricting the computer to 20 qubits, which will not be enough to break the current 1024-bit hashes).


"Real World" Applications of an Efficient Root Finder I don't know this is off-topic (if not, someone can direct me to the proper Stack), but here goes: Let's say there is some algorithm $T$ that can find the integer roots of any arbitrary real-valued continuous univariate function $f(x)$. For any value of $x$, $f$ can be computed efficiently ($O(n^k)$, where $k$ is some small constant). $T$ is similarly efficient. Are there any real life problems that would be benefited by having such an algorithm?

Sure.  If this works for any function $f$ that can be computed efficiently, such an algorithm would let you solve any NP problem.

Let $g:\{0,1\}^n \to \{0,1\}$ be an arbitrary function that is efficiently computable.  When $x$ is an integer, define $f(x) = g(x_1,\dots,x_n)$ where $x_1\cdots x_n$ is the binary representation of $x$; when $x$ is not an integer, define $f(x)$ to linearly interpolate between $f(\lfloor x \rfloor)$ and $f(\lceil x \rceil)$, i.e.,

$$f(x) = f(\lfloor x \rfloor) + (f(\lceil x \rceil) - f(\lfloor x \rfloor))(x - \lfloor x \rfloor).$$

Then if we apply your algorithm to $f$, we find an efficient way to compute $x_1,\dots,x_n$ such that $g(x_1,\dots,x_n)=0$.  This in turn lets you efficiently solve any NP problem.

For instance, you could break the RSA cryptosystem efficiently, you could mint Bitcoin coins efficiently, you could solve optimization and operations research problems efficiently, and so on.

If this is restricted to only $f$ that are low degree polynomials, we already know of algorithms to solve the problem, so it likely would not represent an advance over the state of the art and likely wouldn't have much of an impact in practice, unless your method was significantly more efficient than existing methods.


How do convolution matrices work? How do those matrices work? Do I need to multiple every single pixel? How about the upperleft, upperright, bottomleft and bottomleft pixels where there's no surrounding pixel? And does the matrix work from left to right and from up to bottom or from up to bottom first and then left to right?

Why does this kernel (Edge enhance):

turn into this image:

Convolution matrix are mean to change your image so you have to treat all the pixels.

For pixels without surrounding pixels there are different way to treat than dependently of the result you expect. You can ignore them and get a smaller image. Put an arbitrary value for their surrounding. Or consider the surrounding being symmetrical to the image.

Since the matrix apply on the image it doesn't mater if you apply it up to bottom, left to right or whatever. Each pixel of the result is computed as a local result of the convolution on the image.

For example  for an image
$$\begin{pmatrix}
a &b&c&d\\
e&f&g&h\\
i&j&k&l\\
m&n&o&p
\end{pmatrix}
$$
If we discard the surrounding pixels the result of the convolution with you matrix will be :

$$\begin{pmatrix}
f-e&g-f\\
j-i&k-j
\end{pmatrix}
$$

So for your convolution, a pixel $(i,j)$ is defined as $I_{(i,j)}-I_{(i,j-1)}$.
So this convolution stress the differences between pixels hence show the edges.

I hope its clear.


Gap between numbers in fixed-point vs. floating point arithmetic If $r$ is a machine-representable number and $f(r)$ is the next larger machine representable number, are the following true or false?

In fixed-point arithmetic, the distance between $r$ and $f(r)$ is constant.
In floating-point arithmetic, the relative distance $|(f(r)-r)/r|$ is constant.

I believe that (1) is true, but I'm not sure about (2).  I am new to the world of numerical analysis and I'm just trying to hang on for dear life.  Could anybody point me to a resource that does a good job of explaining the basic introductory topics of machine mathematics?

Yes, the difference is constant.
It is not really constant, but approximately, yes.  With exceptions.

With binary floating point numbers, the expression $(f(r)−r)/r$ is constant within a factor of $2$.  It is between $1 \over 2^m$ and $1 \over 2^{m-1}$ where m is the number of bits in the mantissa.  For rounding error calculations, you can assume it is constant.

A note on 0:
Obviously, you cannot apply the formula when $r=0$.  But it is important to know that while $f(r)-r$ decreases when $r$ becomes small, $f(0)-0$ is much larger than, for instance, $f(f(r))-f(r)$.  There is a huge non-representable gap around $0$.


How does derandomization of 3SAT work via conditional expectations? Given a single SAT clause with its 3 literals coming from 3 different variables it is obvious that  a random assignment of values will satisfy it with probability 7/8

But I do not understand how from the above argument it follows that given a $m$ clause SAT instance the probability of satisfying at least $7/8 - 1/2m$ fraction of the clauses is at least $1/poly(m)$ ?

[..firstly even in a single clause case its not clear how the 7/8 result can hold if variables are repeated - and in the multi-clause case there will now be correlations across clauses - and hence its hardly clear to me as to what is happening!..]

I believe there is some sort of a Markov inequality going on but I can't see it.

Now apparently one can derandomize this using "conditional expectation". (vaguely I understand that it is some way of estimating what is the chance of satisfying the formula when randomizing over a subset of the variables while keeping  the others' values fixed and then probably changing the subset in every round) This is totally unfamiliar to me as to how the above probabilistic argument can be converted into a deterministic one so as to ensure finding of an assignment of values to variables such that always at least 7/8 of the clauses are satisfied.

[..apparently the above can also be thought via "3-wise independent sample space" - if someone can help understand that then that would be great!..]

If you choose an assignment at random, each particular clause is satisfied with probability $7/8$. Using linearity of expectation, this shows that if you choose an assignment at random, then the number of satisfied clauses is at least $(7/8)n$. The idea is to have an indicator variable $X_i$ for clause $i$, which states that the clause is satisfied. Since $\mathbb{E}[X_i] = \Pr[X_i] = 7/8$, by linearity of expectation we have $\mathbb{E}[\sum_{i=1}^m X_i] = (7/8)m$. In particular, some assignment satisfies at least $(7/8)m$ clauses.

Let now $X$ be the number of unsatisfied clauses under a random assignment. Then $\mathbb{E}[X] = (1/8)m$, and so Markov's inequality shows that
$$ \Pr[X \geq (C/8)m] \leq 1/C. $$
By choosing an appropriate $C$ you get your first bullet (try it out!).

Regarding the method of conditional expectations, there are many online resources, for example this one (the first hit on a popular search engine). There are many others.

Finally, if $\mathcal{D}$ is a 3-wise independent sample space – this just means that if $(v_1,\ldots,v_n) \sim \mathcal{D}$, then for any $i<j<k$, the joint distribution of $(v_i,v_j,v_k)$ is uniform over all eight possibilities – then it is still the case that each clause is satisfied with probability exactly $7/8$ (why?). Therefore if we choose a random assignment according to $\mathcal{D}$, the expected number of satisfied assignments is exactly $(7/8)m$. In particular, some assignment in the support of $\mathcal{D}$ – that is, an assignment which is generated by $\mathcal{D}$ with some probability – satisfies at least $(7/8)m$ clauses.

Why is this helpful? There are 3-wise independent samples spaces of polynomial size. We can derandomize the random 3SAT algorithm by taking such a sample space and trying out all assignments in its support. One of them will satisfy at least $(7/8)m$ clauses.


Proving B* = B on a given set I have the set:

B = {x ∈ {0,1}* | there is an equal number of 0's and 1's in x}

and therefore,

B* = {e,01,10,0011,0101,0110,1100,1010,1001,....etc}

I need to either prove or disprove that B*=B

I believe they are equal, because B* is just the concatenation of one string onto another. I think the trick is since the 0's and 1's have to be of equal number, that concatenating strings would keep the same number of 0's and 1's the same.

I just need a little help in the right direction as to prove B*=B. I was thinking of showing that if

B⊆B* and B*⊆B, that B*=B holds.

Any help would be much appreciated!

(Criterion of no-op Kleene star) Let $V$ be a language such that $\epsilon\in V$. Then $V=V^*$ if and only if $V=VV$, where $V^*$ is the Kleene star.

Proof: "$\Longrightarrow$":  $V=V\epsilon\subseteq VV$ while $VV\subseteq V^*=V$.

"$\Longleftarrow$". $V\subseteq V^*$ by definition. Let $V_i$ as defined in Wikipedia. Since $V_0\subseteq V$ and assuming $V_n\subseteq V$, $V_{n+1}=V_nV\subseteq VV=V$, we know $V_i\subseteq V$ for all $i\ge0$ by induction. Hence $$V^*=\bigcup_{i=0}^\infty V_{i+1}\subseteq \bigcup_{i=0}^\infty V=V\,.$$

Exercise 1. Show that $\epsilon\in B$ and $B=BB$.

Exercise 2. Let $V$ be a non-empty language such that $V=VV$. Show that $\epsilon\in V$. (Hence for a non-empty language $V$, $V=V^*$ if and only if $V=VV$.)

Exercise 3. Show that $V^*=(V^*)^*$.


Understanding pipeline stalls (bubbles) based on stage I'm currently reading through x86 Assembly Language and C Fundamentals and came across this statement in the second chapter of the book:

  If the instruction required is not available in the cache, then a cache miss occurs, necessitating a fetch from main memory.  This is referred to as a pipeline stall and delays processing the next instruction.  Information is passed from one stage to the next by means of a storage buffer.

Having read the Wikipedia article associated to this, and the book covering one paragraph of this subject that I can find, I have a few glaring questions regarding this.

Would a pipeline stall occur if there were no further instructions to fetch from main memory, and if so, would it stall for an infinite amount of time until a new instruction was in line from main memory - potentially causing the last operation to never execute?
Can a pipeline stall be triggered at any given stage in the clock cycle, or is it restricted to the fetch and execute stages?
If a pipeline stall occurs due to two stages trying to use the same resources for instruction, does the clock cycle delay by one cycle for both/all of the stages that's trying to use the resource, or is there specificity involved based on stage that would allow for one of the stages to complete its instruction given that the cycle was the cycle in which the pipeline stall occurred?

Note: I'm not formally educated in Computer Science so I apologize if these are CS101 questions.

A CPU pipeline has a number of stages.

The exact stages vary between CPUs and some CPUs have very many stages, but obviously the first stage must be Instruction Fetch (IF) and the second stage must be Instruction decode (ID).
If an instruction is not in the cache it cannot be fetched and delays occur.
Let's call our missing instruction $A$.

The only way for the next instruction $B$ to not be delayed is if $B$ is in the cache and the CPU supports out of order instruction and $B$ does not depend on the outcome of instruction $A$ and the CPU allows fetching from memory and the cache at the same time and the CPU knows where $B$ is located.

Phew that's a lot of if's.
Let's unpack the various issues.

Cache
Because barring jumps instructions are fetched sequentially it's moderately unlikely that $A$ is not cached, whilst $B$ is. But it does happen.

Out of order support
Most CPU's support OoO execution, so there are no problems there.

Independent instruction
Some instructions have no dependencies. e.g. xor rax,rax will zero out rax no matter what.
However we don't know what instruction $A$ does. If it's an unconditional jump it may just jump over $B$.
Still the CPU might elect to execute B speculatively, if the gamble pays off valuable time is gained.

Fetching from memory and cache at the same time
Current x86/x64 CPU's do not support this.
The reason why will become clear in the next paragraph.

Where is $B$ located?
The x86 architecture has a variable length instruction.
A x86/x64 instruction can be anywhere between 1 and 15 instructions long.
Only when the pipeline gets to the Instruction Decode (ID) stage does the CPU know how long the instruction is.
So there is no way for the CPU to know where $B$ starts until $A$ has been decoded.
In normal execution the CPU solves this by either (a) pre-decode instructions and store the instruction lengths in the cache (as meta data), or (b) fetch large chunks of data in one go and parallel decode this or both.
Intel uses strategy b, AMD uses a+b.

However it is impossible to know where $B$ starts without knowing the instruction length of $A$.
There are 15 possible lengths and the CPU will not start 15 possible speculative executions, that's would just be a waste of silicon :-).

If the x86 architecture had fixed instruction length then speculative execution would have been an option. The fetch and decode stages pose no problem and perhaps even more stages could be performed.
However CISC and variable instruction length throws a big spanner in the works.

  Can a pipeline stall be triggered at any given stage in the clock cycle, or is it restricted to the fetch and execute stages?

The details are very complex, but, yes, a stall can and does occur at every stage.
Common stall reasons are:

mispredicted jumps. This causes a stall because the pipeline needs to be emptied and reread from some as yet unknown address.
instruction $B$ depends on the outcome of instruction $A$. This is called a dependency chain. These chains can be arbitrary long.
both instructions $A$ and $B$ require some piece of expensive hardware. The CPU has only one of these available and thus $B$ must wait for $A$ to finish.

  If a pipeline stall occurs due to two stages trying to use the same resources for instruction, does the clock cycle delay by one cycle

That depends if the resource allows pipelining.
In modern CPU's the answer is yes. Expensive hardware is capable of pipelined operation.
E.g. two multiplication instructions will execute in 4 cycles given that a MUL reg,reg has a 3 cycle latency and a third unrelated instruction can execute in parallel.

  would it stall for an infinite amount of time until a new instruction was in line from main memory - potentially causing the last operation to never execute?

Yes, e.g. if the memory has been swapped out to disk and the disk takes indefinitely long the CPU will just wait.
Well the hardware will generate a page fault exception, but that's beside the point


How to make a parse tree for the following propositional logic formula? I have a formula $ \neg((q \implies \neg q) \vee p \vee (\neg q \implies (r \wedge p))) $.

As it contains 3 subformulas between the $\vee$'s, how can i put it into a parse tree, as a parse tree contains 2 branches from each node.

As it is, your formula is ambiguous; it is not clear which pair of parentheses to insert in order to get a binary tree. Both

$\qquad \displaystyle \varphi_1 \lor (\varphi_2 \lor \varphi_3)$

and

$\qquad \displaystyle (\varphi_1 \lor \varphi_2) \lor \varphi_3$

are feasible. Luckily for you, $\lor$ is associative, so you can choose either one:

[source]

For the purposes of parsing, you would either require formulae to be completely parenthesised, or specify operators to be left- (or right-) associative. Operator precedences would be the next thing to look into, in order to disambiguate formulae like

$\qquad \displaystyle a \land b \lor c$.