Algorithm to find smallest difference in array We want an algorithm that, given an array of length $n$ of integers, find the minimum difference between two integers in the array.

One such algorithm is to sort the array and check adjacent pairs of numbers. This takes time $O(n\log n)$.

Is there a faster way, e.g., an $O(n)$ algorithm?

This depends on your model of computation. If you only allow arithmetic and comparisons (the algebraic decision tree model) then there is an $\Omega(n\log n)$ lower bound for element distinctness, the problem of deciding whether all elements are distinct. Your problem is of course even harder, so the same lower bound applies.

(There is some fine print: the lower bound only holds if the degree of the polynomials being compared is bounded. If all you're doing is comparing various differences $x_i - x_j$, then you're good to go. The algebraic decision tree model also allows you to compare more general polynomials in the inputs, as long as they have bounded degree.)

There are other models which might perform better — for example, in some models you can sort integers in $o(n\log n)$. But I imagine you don't want to allow the sort of trickery used in such algorithms.


Randomly choose vector b in range such that $\vec{a} \cdot \vec{b} = 1$ Given

I have a $n$ dimensional $\vec{a}$.
All elements of $\vec{a}$ are between 0 and a positive number $K$.
$n$ is about 15 to 20.

Problem

I want to randomly and unbiasedly choose a vector $\vec{b}$ such that:

Elements of $\vec{b}$ are between 0 and 1.
$\vec{a} \cdot \vec{b} = 1$

How to do that?

Attempt

I thought about the following:

Choose $\vec{c}$, a random direction perpendicular to $\vec{b}$.
Find range of $\theta$ such that $\vec{b} = \frac{\vec{a}}{\lVert \vec{a} \rVert} + \theta\vec{c}$ is within bounds.
Randoly choose a $\theta$

The problem is that this is not unbiased. Some directions have a larger range of legal $\theta$, and those directions should be chosen more often.

Uniformly sampling from a simplex with equation $\vec{a} \cdot \vec{b} = 1$, and reject samples out of bounds.

Several answers are posted here for uniform sampling over a simplex: Uniform sampling from a simplex


What are the simplest examples of programs that we do not know whether they terminate? The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not. What are the simplest (smallest) known examples of such programs?

A pretty simple example could be a program testing the Collatz conjecture:
$$
f(n) =
\begin{cases}
\text{HALT}, &\text{if $n$ is 1} \\
f(n/2),  & \text{if $n$ is even} \\
f(3n+1), & \text{if $n$ is odd}
\end{cases}
$$
It's known to halt for $n$ up to at least $5 × 2^{60} ≈ 5.764 × 10^{18}$, but in general it's an open problem.


How to pack polygons inside another polygon? I have ordered a few leather sheets from which I would like to build juggling balls by sewing edges together. I'm using the Platonic solids for the shape of the balls.

I can scan the leather sheets and generate a polygon that approximates the shape of the leather sheet (as you know, it's animal skin, and it doesn't come in rectangles).

So now, I would like to maximize the size of my juggling ball.

In my example, the polygons are regular ones, but I'm looking for a solution with simple polygons.

What is the largest scale factor that I can apply to my polygons so that they all fit inside the sheet ?

I am trying to minimize the waste by using as much as material as possible.

Obviously, cutting the polyhedron net into individual polygon will increase the space of possible combination, but also decrease the quality of the final geometry, because there is more sewing involved and accumulated errors. But this question is not about enumerating the different ways of unfolding a polyhedron. They can be considered independently. So the polygons are simple polygons.

Formally:

Input:

$P$ : a simple polygon (the target)
$S$ : the set of polygons I want to place
$G$ : a graph of $n$ simple polygons - each node represents a simple polygon in $S$, and there is one edge edge between each pair of polygons that share a common edge
$\alpha >= 0, \beta >= 0$ (usage of material and connectivity)

Output:

a scale factor $f$
$H$, a subgraph of $G$
$Loc$: a location and an angle for each polygon in $V(G)$
a measure of the quality $m$ of the solution: $ m = \alpha.f + \beta. {|E(H)|\over|E(G)|} $

Maximize $m$ subject to these conditions:

$ | V(H) | =  |V(G)| $  (1)
$ | E(H) | <= |E(G)| $  (2)
for every polygon $S_i$ in $S$, $S_i$ scaled by a factor $f$ at location $Loc(S_i)$ is inside $P$ (3)
polygons in $V(H)$ don't overlap (4)

( V(G) are the vertices in the graph, and S is the set of polygons, but they describe the same set of objects. Maybe there is a more compact way to do this.)

Explanation of the conditions:

(1) I want all the polygons to be in the final layout
(2) Some connections may be broken if necessary
(3) (4) the ball is made of leather

Here is the target polygon

Here is the set of polygons I want to pack:

This belongs to an optimization class of problems called Packing problems. In your case, instead of a regular polygon as container, you've got an irregular one, but the idea remains the same.
These optimization problems are usually NP-hard, so I don't think there is an easy way to get the exact solution and trying all the combinations would be too too expensive.
There are some people interested in this kind of problems; I've found this link of some solved specific packing problems: https://erich-friedman.github.io/packing/
The easiest way I see, is to define an approximate center of the leather sheet, to move the set of polygons to there and, by scaling up and down and checking if the set of polygons is or not inside the target polygon, to get a closer and closer scale factor 'f' for your desired set of polygons.
But, unless you are going to use this factor for a large scale juggling balls production, probably doing it by hand would be fairly enough.


Finding shortest path from a node to any node of a particular type I have an un-directed, un-weighted graph G.Starting from a given node A, i want to find whether there is a path from A to a node of a certain type .There can be many nodes of that type. The problem is to find the shortest path from A to any such node, if it exists.
This can be achieved by doing a breadth first search which would give the shortest distance between A and the desired node if it exists. Given that the graph can be pretty dense, what could be a better algorithm to achieve this? Both memory and time taken for the search are to be kept in mind while designing this.

If such queries could be optimized by doing some pre-processing while the graph is built, such additional hit on performance could be acceptable (not memory though).

I don't have enough rep to comment, but here are some suggestions rather than a definitive answer. These algorithms assume the graph is fixed.

Let $k$ be the number of types. The number of nodes is $n$, similarly $m$ for edges.

Case 1: $k$ is acceptably small.

Strategy: Just store the info.

Preprocessing: $\mathcal{O}(k(n + m))$,
Memory: $\mathcal{O}(kn + m)$,
Query Time: $\mathcal{O}(1)$

Simply store the shortest distance to any type for each node. This can be done in $\mathcal{O}(k)$ space per node. The values can be obtained by running BFS $k$ times,  once for each type. Let $D[v][t]$ be the distance from node $v$ to any node of type $t$, initialized to $\infty$.

For each type $t$, find the connected component of nodes of just that type, by BFS. During the BFS, keep a set (the "boundary" nodes) of all nodes of other types that are encountered. Now BFS using that set as a starting point, record the distance in $D[v][t]$ for each node encountered. Runtime is $\mathcal{O}(n + m)$ for each type $t$.

Querying: $\mathcal{O}(1)$, just look up the value in $D$.

Case 2: $k$ is not that small. But the graph is very dense.

Strategy: Utilize bidirectional search after graph transform.

Preprocessing: $\mathcal{O}(n + m)$, Memory: $\mathcal{O}(n + m)$

Query Time: $\mathcal{O}(n + m)$ (but possibly better in practice, see: http://en.wikipedia.org/wiki/Bidirectional_search)

We will be adding nodes / edges and transforming the undirected graph into a directed one.

Create $k$ supernodes, $S[t]$, one for each type. For edges that link different types of nodes: $e_{u,v}$ where $type(u) \neq type(v)$, create additional edges from $v$ and $u$ directly to the supernode of the other type (directed into the supernode). Next convert all the original undirected edges into two directed edges, one in each direction.

At most, we've added $n + m$ extra links and $k < n$ (assuming a node can belong to only one type) extra nodes, preserving the memory and time bounds. The transformation itself takes $\mathcal{O}(n + m)$ time. Essentially, the supernodes allow us to search in both directions, without affecting correctness. While we BFS from the starting node, we can also BFS in reverse from the supernode of the target type. This can be more efficient if the nodes originally had large degrees (big branching factor).

Querying: To find the shortest path from node $v$ to type $t$, run a bidirectional BFS from $v$ and $S[t]$. Depending on the graph, this could be significantly faster than just a BFS for very dense graphs, and will not be asymptotically slower.


Sabatier conjectures While I was doing
CLRS (3rd
edition), I came across this question on page 629:

Professor Sabatier conjectures the following converse of Theorem
23.1:

  Let $G = (V,E)$ be a connected, undirected graph with a real-valued
   weight function $w$ defined on $E$. Let $A \subseteq E$ that is
   included in some minimum spanning tree for $G$, let $(S,V -S)$ be any cut of $G$ that respects $A$, and let $(u,v)$ be a safe
   edge for $A$ crossing $(S, V - S)$. Then, $(u,v)$ is a light
   edge for the cut.

Show that the professor’s conjecture is incorrect by giving a
counterexample.

Theorem 23.1:

  Let $G = (V,E)$ be a connected, undirected graph with a real-valued
   weight function $w$ defined on $E$. Let $A$ be a subset of $E$ that
   is included in some minimum spanning tree for $G$, let $(S, V
 - S)$ be any cut of $G$ that respects $A$, and let $(u,v)$
   be a light edge crossing $(S, V - S)$.  Then, edge $(u,v)$
   is safe for $A$.

Can anybody please give a proof or a counterexample to the conjecture
also because I used to think that all safe edges added to the graph
are light edges.

  DEFINITIONS :
  1. Cut (S ,V-S) : of an undirected graph G = (V,E) is a partition of V(as defined in CLRS Book) .You can think it as a line that divides graph into two disjoint sets of vertices on its either side.
  2. Light edge:Any edge crossing a cut is light edge if its weight is the minimum of all the edge crossing the cut.Light edge is defined with respect to a particular Cut.
  3. A cut Respects a set A of edges if no edge in A crosses the cut.
  4. Safe edge is the edge which we can add to MST without any violation of MST's property.These are those edges which are the part of final MST.

I have written most of the definition but for more queries you can also refer to CLRS chapter 23.

OK, here's a big hint.

Take any $G,A,S$ that satisfy the premises of the question.  Now add a new vertex $v'$ to the graph, and draw an edge from $v'$ to one of the vertices of $A$ with a weight of your choice.  (This means that $v'$ will be connected to the rest of the graph only by this one new edge; there are no other edges out of $v'$.)

What can you say about this new edge?  Does it cross the cut?  Is it a light edge?  Is it a safe edge?  Does this suggest any method for choosing the weight on that edge, to make things fortuitous to you?  Hint: if you think about it (or try some examples), I bet you'll see how you can arrange things to get a violation of the conjecture.

People learn best by finding the solution for themselves (rather than reading someone else's solution), so I'm not going to post more than a hint.  This hint ought to be enough to understand what's going on here....


Was there an attempt to make reusable regular expressions? In everyday practice I often encounter tasks which would benefit from being able to define aliases for chunks of regular expressions to reuse them later. Typical examples include: parsing a floating point number, a zip code or a telephone number. (Zip code may become particularly unwieldy).

Suppose you could define a grammar for parsing floating point numbers, and then give it an alias, once defined you would be able to reuse this in regular expressions you use afterwards. In some fictional language this could look like this:

float := /[+-]?(\d+|\d*\.d+)(e\d+)?/
sum := /(?R<float>)+(?R<float>)/

This, in principle, wouldn't change anything in terms of expressive power (unless you allow self-reference), but it seems like it could make the practical implementations of regular expressions more concise?

So, my question is: has any language implemented anything like that? Or, and if not, then what would be the reason for not doing so?

Lex, the lexical analyser generator, supports this notation. In the "definitions" section, you can define patterns which you can then use in the "rules" section:

DIGIT    [0-9]

%%

{DIGIT}+"."{DIGIT}*  { return T_FNUM; }

Most lexer generators have something similar; ANTLR has "fragments", for example.


Starting BFS at s and t INPUT: undirected graph, s, t

OUTPUT: connectivity of s and t

I perform BFS on s AND t, each taking turns to make one traversal.

When a vertex exists in both s and t's BFS tree, we can assume it is connected.

When one tree is done traversing but the other is not, s and t are not connected.

Does such an algorithm exist or am I making stuff up?

Yes, this is a known thing. It's called bidirectional search.  It will find shortest paths in unweighted graphs and, in graphs of where every vertex has degree $d$, it will visit at most $2d^{\ell/2}=2\sqrt{d^\ell}$ vertices (where $\ell$ is the length of the shortest path), whereas ordinary BFS could visit up to $d^\ell$ vertices.


Robust two lines/segments intersection point in 2D Given two line segments the problem is to find an intersection point of corresponding lines (assuming that they are not parallel or coincide).

There is a Wikipedia article which gives us exact formulas, but there are two of them: one that uses t ratio and approaches intersection point from first line segment and the other -- uses u and the second line segment. How can I select which one to use in my scenario?

For example: my initial implementation which always used t failed on

first_segment = Segment(start=Point(x=-5, y=0), end=Point(x=72057594037954921, y=0))
second_segment = Segment(start=Point(x=0, y=0), end=Point(x=0, y=3))

gives

Point(x=5.921189464665284e-16, y=0.0)

which is incorrect, but when I switch to use u or change order of arguments it gives me correct

Point(x=0.0, y=0.0)

So my question is: is there robust way to calculate intersection point?

If you choose a formula with parameter $t$ you'll get the $P_x$ value as a result of a number of operations - additions, multiplications and one division:

$$t = \frac{(x_1-x_3)(y_3-y_4)-(y_1-y_3)(x_3-x_4)}{(x_1-x_2)(y_3-y_4)-(y_1-y_2)(x_3-x_4)}$$
$$P_x = x_1 + t(x_2-x_1)$$

The number $x_2=72057594037954921$ contains 17 significant decimal digits - so it can't be represented exactly using double-precision floating numbers. Apparently, a small error is introduced during some operation (most probably - the division), and this error is propagated to the result. This is a form of the Round-off error.

This bunch of calculations doesn't happen when you choose a formula with parameter $u$, because the numerator there is equal to zero.

Conclusion: if you need to work with numbers, containing a big number of significant digits - use floating numbers with bigger precision, or may be - with arbitrary precision. An example: mpmath.

Another option - use rational numbers. For example, kernels, based on rational numbers, can be found in the computational geometry library CGAL. Developers of this library have invested a lot of efforts to solve this robustness problem - please see this page for more information.

If you want to go deeper into this research area, called Exact Geometric Computation (EGC), you can start from this review. You'll need a good knowledge of Linear Algebra and Linear Systems.


How many ways to express N as sum of 2, 3 and 5? I've learnt about problems about express N as sum of 2, 3, 5. For examples, if N = 7:

N = 5 + 2
N = 2 + 5
N = 2 + 2 + 3
N = 2 + 3 + 2
N = 3 + 2 + 2

But most of I found on the Internet that the different position is different way to express N (as this link for expressing N as sum of 1, 3, 4). Following that link, I try following DP formula:

    f[0] = f[1] = 0 ;
    f[2] = f[3] = f[4] = 1;
    for(int i = 5; i < 100; i++) {
        f[i] = f[i-2] + f[i-3] + f[i-5];
    }

But it isn't correct, as N = 7, F[N] = 4. So what is the correct DP method for this problem?

Hard version: I also concern about don't care order of way to express N, such as N = 2 + 2 + 3 and N = 2 + 3 + 2 and N = 3 + 2 + 2 will be only count as 1 time.

Note that I'm trying to solve above problem in complexity O(N).

It looks like you're missing some considerations with respect to the base cases. Since you're starting your for loop at i = 5, you should have base cases set for i = 0, 1, 2, 3, 4. f[0] = 1 since there's 1 way to choose a set of numbers that sums to 0 — choose nothing. f[1] = 0 since there's no way to make 1 out of 2, 3, and 5. f[2] and f[3] are both equal to 1 because they are in your set. Finally, f[4] = 1, since 2+2 = 4. This gives output f[7] = 5, as shown in your example cases.

For the "harder version", I suggest you look up the coin change problem. The problem formulation is essentially the same — how many ways are there to make up a given sum using a set of coins? The basic idea, and the one that prevents doubly counting permutations of the same solution, is that for each coin or value, you consider whether or not you wish to include it in the current solution set. If so, you get closer to the sum, and you can choose to reuse the same coin/value. If not, the value of your solution stays the same, but you never use that coin/value again in that solution. The final number of ways is just the sum of these two possibilities. Note that this method does have a time complexity of $O(mn)$.

Additional Links

https://www.geeksforgeeks.org/coin-change-dp-7/


Why are both caller-save registers and callee save registers needed? I am having a difficult time understanding callee and caller-save registers. I get that caller-save registers are those which are needed after function call and hence caller saves them in caller prologue and restored in caller epilogue. Callee-save are those who are used by callee and are saved in callee prologue and restored in callee epilogue. But why are both needed? If caller is saving the needed registers already, why should callee save them again on use? I am really confused.

Let's see. CPU have, f.e., 16 registers. If subroutine modifies them, they should be saved before that and restored later. Now, who should do that?

All 16 registers can be saved by caller, or all 16 registers can be saved by callee, or mixed scheme may be used. In this schema, 8 registers is considered as transient - caller don't expect that their contents will be left intact after a call. Thus callers usually use these registers only for temporary data, i.e. computations between calls. But in a few cases when these registers contains non-transient data, caller has to save their contents.

Other registers are considered as permanent, so caller expects that they are left untouched by callee. But in the cases when callee really needs to use more registers, it needs to save/restore their contents.

Why hybrid scheme is advantageous - because usually each procedure needs a few registers for transient data, so by having convention that these registers can be modified by callee, you can reduce calling sequence and therefore make procedure calls a bit faster and more compact.

OTOH, if we consider some registers as "permanent", we can try to avoid using these registers in leaf procedures (i.e. those not calling other procedures) and avoid saving/restoring these registers in leaf procedures. Since cpu usually spends most of time in leaf procedures, this also means quite substantial speed improvement.

So, by splitting registers into two classes, we can make program faster and shorter - leaf subroutines try to not use "permanent" registers and as result don't need to save/restore any. OTOH, other procedures try to don't use "transient" registers to hold values through calls, thus avoiding need to save/restore them.

So, hybrid scheme makes program more efficient compared to any of two pure schemes.


Can one show NP-hardness by Turing reductions? In the paper Complexity of the Frobenius Problem by Ramírez-Alfonsín, a problem was proved to be NP-complete using Turing reductions.
Is that possible? How exactly? I thought this was only possible by a polynomial time many one reduction. Are there any references about this?
Are there two different notions of NP-hardness, even NP-completeness? But then I am confused, because from a practical viewpoint, if I want to show that my problem is NP-hard, which do I use?
They started the description as follows:

A  polynomial  time  Turing  reduction from  a problem $P_1$  to  another problem $P_2$  is  an  algorithm  A  which  solves  $P_1$  by  using  a  hypothetical  subroutine A'  for  solving  $P_2$  such  that,  if  A' were  a  polynomial  time  algorithm  for  $P_2$  then  A would  be  a  polynomial  time  algorithm  for  $P_1$.  We  say  that  $P_1$  can  be  Turing  reduced to  $P_2$.
A  problem  $P_1$  is  called  (Turing)  NP-hard  if  there  is  an  NP-complete  decision
problem $P_2$  such  that  $P_2$  can  be  Turing  reduced  to  $P_1$.

And then they use such a Turing reduction from an NP-complete problem to show NP-completeness of some other problem.

There are (at least) two different notions of NP-hardness. The usual notion, which uses Karp reductions, states that a language $L$ is NP-hard if every language in NP Karp-reduces to $L$. If we change Karp reductions to Cook reductions, we get a different notion. Every language which is Karp-NP-hard is also Cook-NP-hard, but the converse is probably false. Suppose that NP is different from coNP, and take your favorite NP-complete language $L$. Then the complement of $L$ is Cook-NP-hard but not Karp-NP-hard.

The reason that $\overline{L}$ is Cook-NP-hard is the following: take any language $M$ in NP. Since $L$ is NP-hard, there is a polytime function $f$ such that $x \in M$ iff $f(x) \in L$ iff $f(x) \notin \overline{L}$. A Cook reduction from $M$ to $\overline{L}$ takes $x$, computes $f(x)$, checks whether $f(x) \in L$, and outputs the converse.

The reason that $\overline{L}$ is not NP-hard (assuming NP is different from coNP) is the following. Suppose $\overline{L}$ were NP-hard. Then for every language $M$ in coNP, there is a polytime reduction $f$ such that $x \in \overline{M}$ iff $f(x) \in \overline{L}$, or in other words, $x \in M$ iff $f(x) \in L$. Since $L$ is in NP, this shows that $M$ is in NP, and so coNP$\subseteq$NP. This immediately implies that NP$\subseteq$coNP, and so NP=coNP.

If some Cook-NP-hard language $L$ is in P, then P=NP: for any language $M$ in NP, use the Cook reduction to $L$ to give a polytime algorithm for $M$. So in that sense, Cook-NP-complete languages are also "hardest in NP". On the other hand, it is easy to see that Cook-NP-hard=Cook-coNP-hard: a Cook reduction for $L$ can be converted to a Cook reduction for $\overline{L}$. So we lose some precision by using Cook reductions.

There are probably other shortcomings to using Cook reductions, but I'll leave that to other answerers.


Error correcting permutation code Let's say you have $n$ symbols. You can encode a $\log_2(n!)$-bit message by permutating the symbols. I will call this a permutation code (if you have seen this concept before, I would love to see a reference).

Let's say we are encoding a message with $k<\log_2(n!)$ bits. It is possible to add error correction. One way is to simply add any old error correction scheme to the string before applying the permutation code. I'm wondering if there is a way that is optimal for permutation codes.

In particular, is there some way of doing a permutation coding that is resistant to transpositions (in terms of error detection and correction)?  I want something that will tolerate up to $t$ transpositions of adjacent symbols.

The first reference seems to be Rank permutation group codes based on Kendall's correlation statistic by Chadwick and Kurz; your notion of distance is known as Kendall's tau distance. A more modern reference is Codes in Permutations and Error Correction for
Rank Modulation by Alexander Barg and Arya Mazumdar


What is the difference between centralised, decentralised, distributed, fully-distributed? What is the difference between centralised, decentralised, distributed, fully-distributed, partially-centralised, partially-decentralised system?
Which type or topology is the system attached in the picture below? For instance, A is a master node (coordinator) of A1, A2, A3, which makes this part a centralised system. A, B, C and D are all connected between each other, which makes this system a decentralised one. But then, what are fully-distributed, partially-centralised, partially-decentralised systems?

You need to differentiate between centralization/decentralization on the one hand and distributed/non-distributed on the other hand.

Centralization
Centralization tells you where the processing gets done.
Fully centralized systems do all their processing in one place.

Distribution
Distribution has nothing to do with processing. It just relates to systems that communicate via messages.
A non-distributed system is a stand-alone PC with no clients, or a server with dumb clients.

A fully distributed system does not have a single source of truth, however that does not mean that all nodes have to be equal. You can have 'supernodes' mixed with lesser nodes and still be fully distributed.

Distribution = network
The current incarnation of distributed systems are networked systems, but of course it's perfectly possible to pass messages using a serial cable, sneakernet or carrier pigeon. Is that a distributed system?
Yes if both systems do actual work, No if one system is simply a recipient of data (printer/terminal etc).

Peripherals do not count
The passing of screen and keyboard data between the terminal and the server is not deemed substantial enough to qualify as message passing.

Caveat
The definition of distributed computing is best narrowed down in the context of a specific protocol or algorithm (e.g. bittorrent or mapreduce)
Outside that context it becomes exceedingly vague to the point of being meaningless.

The mysterious diagram
The diagram in the question seems to hint at some sort of hierarchy and thus centralisation.
Obviously the systems A,B,C and D cannot be peripherals (because they are not leaf nodes) and thus some message passing (aka network activity) ought to take place.
What the nature of the leaf nodes (A123 et al) is is unclear, but these leafs do seem subservient to A,B and C proper.


Show that some context free languages must contain more that one non-terminal Context free languages that has only one non-terminal is a proper subset of context free languages and they does not contains regular set. Since, CFL is more powerful than FSM and contains regular set, there must be some languages that requires more than one non-terminal. How can I show or proof this formally?

Consider the language $L=\{a^mb^{m+n}a^n\ |\ m,n\ge 1\}$. From the assumption that there is a single-nonterminal CFG $G$ for $L$, we can derive constraints which eventually lead to a contradiction.

$G$ is given by the (singleton) set $\{S\}$ of nonterminals, set $\{a,b\}$ of terminals, and some number of rules $S\to w_i$ for $w_i\in\{a,b,S\}^*$. There are some obvious conditions:

There must be some $i$ such that $w_i$ contains $a$.
There must be some $j$ such that $w_j$ contains $b$.
There must be some $k$ with $w_k\in\{a,b\}^*$.

Note that some of $i,j,k$ might coincide, but this does not matter. Now suppose that there is some $l$ such that $w_l$ contains more than one $S$, i.e. $w_l=xSySz$ for some $x,y,z$. Then
$S\to xSySz\to xxSySzySz\to\dots\to xxw_jyw_izyw_jz$ which contains a $b\dots a\dots b$ subsequence, i.e. we get a word outside $L$ (once any  additional $S$ which might occur inside $x,y,z$ are replaced with $w_k$).

So the rules in $G$ really can only be of the forms $S\to u_iSv_i$ or $S\to w_i$ with $u_i,v_i,w_i\in\{a,b\}^*$. Since we can only use one of the latter form when building a word, and we may need arbitrarily many $b$, we get

For some $i$, either $u_i$ or $v_i$ contains a $b$. We will assume wlog that it is $v_i$; the $u_i$ case is symmetric.

Suppose that there is also a $j$ such that $v_j$ contains $a$; then $S\to u_iSv_i\to u_ju_iSv_iv_j\to u_iu_ju_iSv_iv_jv_i$, which again contains a $b\dots a\dots b$ subsequence and takes us out of $L$. Therefore

$v_i\in b^*$ for all $i$.

But the words in $L$ all end with an $a$, so

$v_i=\epsilon$ for all $i$.

But then $G$ is a regular grammar and cannot generate a non-regular language like $L$.


Why is $L=wxw^R|w,x\in\{0,1\}^+$ regular? I was taught that if you can create a DFA to accept a language, then the grammar that is generating the language is regular.

AND

A DFA is a finite automata that accepts a language and also rejects the strings that aren't a part of the language.

It says if we replace $x$ with $c$ where $c \in \{0,1\}^+$, then $L$ is regular.

But the DFA should reject the string $abbaaaba$ since it doesn't fit the $wxw^R$ criteria and that isn't happening, so how is it regular?

In $\{wxw^R|w,x\in\{0,1\}^+\}$, we're free to choose $x$ to be any non-empty sequence, including all but the first and last characters of $wxw^R$. So we might as well limit $w$ to be a single symbol; it won't change anything.

So $L$ is exactly the same as $L' = \{axa|a\in\{0,1\}\land x\in\{0,1\}^+\}$ which is evidently regular.

Here's a more formal proof, in case the above was too telegraphic. Suppose we have

$$L = \{wxw^R|w,x\in\{0,1\}^+\}$$

Now:

$$\{0,1\}^+ \equiv \{0,1\} \cup \{aw | a \in \{0,1\} \land w \in \{0,1\}^+$$

which just says that $w^+$ is either exactly one symbol or one symbol concatenated with $w^+$. Also observe that if $a$ is a symbol and $w$ is a sequence of symbols, then $a^R\equiv a$ and $(aw)^R\equiv w^Ra$. So we can rewrite $L$ as a union:

$$L = \{axa|a\in\{0,1\}\land x\in\{0,1\}^+\} \cup \{awxw^Ra|a\in\{0,1\}\land w,x\in\{0,1\}^+\}$$

Now, looking at the two sets in that union, we can see that

$$\{awxw^Ra|a\in\{0,1\}\land w,x\in\{0,1\}^+\} \subset \{axa|a\in\{0,1\}\land x\in\{0,1\}^+\}$$

because

$$\{wxw^R|w,x\in\{0,1\}^+\} \subset \{0,1\}^+$$

and since for any sets $A$ and $B$

$$B \subset A \implies A = A \cup B$$

We can simplify the definition of $L$ to

$$L = \{axa|a\in\{0,1\}\land x\in\{0,1\}^+\}$$

which is clearly a regular language.


If a problem Q is NP complete, is another problem reducible to Q also NP complete? Let's say $\mathcal{P}$ is a yes/no prolem with an existing reduction to the problem $\mathcal{Q}$ (with time complexity $\mathcal{O}(n^2)$). $\mathcal{Q}$ is NP complete. Does this mean that $\mathcal{P}$ is also NP complete?

Not necessarily. Any language in $\mathbf{P}$ is poly-time many-one reducible to any non-trivial language (i.e., all except $\varnothing$ or $\Sigma^\ast$); see here, for example. The latter language (i.e., the one you are reducing to) is, in this case, the $\mathbf{NP}$-complete $\mathcal{Q}$. For all we know, your language $\mathcal{P}$ could be any language in $\mathbf{P}$ and, therefore, not necessarily $\mathbf{NP}$-complete (even under the assumption $\mathbf{P} = \mathbf{NP}$).


Algorithm to calculate numbers of 10^x smaller than given one I am struggling to create a smart algorithm. Currently I have produced one which is super-ugly and not efficient because I am casting numerics to strings back and forth, not really useful to share it here.

The point of algorithm is to get a number 10^x which is smaller than a given one.

Examples:

600 => 100
34.54 => 10
7.2 => 1
0.123 => 0.1

I am sure I am missing something. Is there any smart way of doing that?

$Num \geq 10^{x} $

$\implies x \leq log_{10}(Num)$

Then $x = \lfloor log_{10}(Num) \rfloor $.

$10^{x}$ would be your number.


Proving the Language is not regular for $(a^n)^n$ I am trying to solve a pumping Lemma Problem where $L= \{(a^n)^n ; n\ge 0\}$
I am having a lot of trouble with the pumping lemma and understanding using it with different languages. Here is what I have so far and would appreciate any input on it.

Assume for contradiction that $L$ is a regular language. Since $L$ is infinite we can apply the pumping Lemma. Let $p$ be the critical length for $L$.

Let $w = (a^p)^p$ and length of $|w|>=p$. From the pumping lemma we can write $w = (a^p)^p = xyz$. With
$|xy| \le p$ and $|y| \ge 1$. Thus $y = a^k, 1\le k\le p$. So for $xy^iz \in L$ we can take $xy^0z = xz = (a^{p-k})^p$ which should be contained in $L$ but since it is not we have a contradiction thus the language is not regular.

Any help or recommendations is appreciated, thank you.

You're on the right track. Here are a few missing details. First, note that $(a^n)^n=a^{n^2}$, so you want to prove that $L=\{a^{n^2}\mid n\ge 0\}$ isn't regular.

Assume $L$ is regular. Since $L$ is infinite, there's an integer $p$ for which the PL applies, so choose $s=a^{p^2}$ and write $s=xyz$ with $|xy|\le p$ and $|y|\ge 1$. Hence, $y=a^k$ with $1\le k\le p$. Then the PL implies that $xz\in L$. Thus we know that $|xz| =p^2-k$, [You goofed here.] and since $k\le p$, we have
$$
|xz| =p^2-k\ge p^2-p >p^2-2p+1=(p-1)^2
$$
and so $(p-1)^2< |xz|<p^2$ and so $xz\notin L$, since $xz$ lies strictly between two adjacent (lengthwise) elements in $L$ and so can't be in $L$, a contradiction.

[The only way this could fail is if $-p\le -2p+1$ and that only holds when $p\le 1$ which we know must be true, since $p$ is the number of states of a FA that accepts $L$ and clearly a one-state FA won't recognize $L$.]


Is there a fundamental CS problem in ORMs that leads to N+1? Many of us are familiar with N+1 problem when working with database queries. The problem was known before ORMs (Object-relational mapping frameworks) came around, but it seems that ORMs exacerbated it.

The problem goes like this. If your database has a table of cars and each car has a list of wheels (stored in another table), if you first query for all cars (1) and then for each car you query for its wheels (N) you get orders of magnitude less efficient query because you in fact have N+1 queries, whereas you could just have one.

I'll show you one scenario in which it is difficult for a less experienced developer to spot that they have an N+1 problem while using ORM.

Let's assume we have the following tables definition in Microsoft Sql Server:

CREATE TABLE [dbo].[Article](
  [Id] [int] IDENTITY(1,1) NOT NULL,
  [Title] [nvarchar](max) NULL,
CONSTRAINT [PK_dbo.Article] PRIMARY KEY CLUSTERED ([Id] ASC)
)
GO

CREATE TABLE [dbo].[ArticleScore](
  [Id] [int] IDENTITY(1,1) NOT NULL,
  [ArticleId] [int] NOT NULL,
  [ActualCity] [nvarchar](10) NULL,
  [Score] [int] NOT NULL,
 CONSTRAINT [PK_dbo.ArticleScore] PRIMARY KEY CLUSTERED ([Id] ASC)
)

GO

ALTER TABLE [dbo].[ArticleScore]  WITH CHECK ADD  CONSTRAINT [FK_dbo.ArticleScore_dbo.Article_ArticleId] FOREIGN KEY([ArticleId])
REFERENCES [dbo].[Article] ([Id])
GO

There is nothing fancy here, the main thing is that we have two tables that have a foreign key relationship.

Now let's assume that we use EntityFramework, and somewhere in the code we have a line like this:

var scores = context.ArticleScores.Where(x => x.Score < 100).ToList();

Now the scores list gets passed around a few methods, and somewhere else it's used like this:

var filtered = scores.Where(x => x.Article.Title != "trash").ToList();

This last line will cause a separate query to be executed for each Article object. When the number of objects are large, the overhead as we all know serious.

Full example that can be run and examined in SQL Profiler can be found here, which is adapted from here but I hope that the idea is clear.

The problem with this particular case can be solved with eager loading, and Entity Framework offers Include method that would load Article objects along with ArticleScore objects in the first query, thus eliminating the need to query the database at all for the second query.

Now to my question.

I would (apparently incorrectly) imagine, that there should be enough information for ORM to execute the second query in a single sql query, thus reducing N+1 problem to 1+1 problem which, in most cases won't be a problem.

ORM knows about relationship between Article table and ArticleScore table. It knows that conceptually a list of ArticleScore objects represent a slice of ArticleScore table. Thus it should be able to figure out how to get the corresponding slice of the Article table in one query, it does not look like a rocket science.

So could you please tell me, is there some fundamental problem, when writing ORMs, that would prevent elimination of most of the N+1 problems?

I understand that you cannot prevent someone from shooting oneself in the foot by writing specifically incorrect code, but in the examples like the one given above many people can easily miss the problem altogether, which is apparent to me after a few code reviews I conducted. To many people this code looks like it should have worked without exhibiting N+1.

Challenge #1: Imperative code

You've shown code that is in a nicely functional form.  But in many languages, in many cases, the code won't be in that nice form.  Imagine if instead of

var filtered = scores.Where(x => x.Article.Title != "trash").ToList();

the code is instead

var filtered = new List();
for (x in scores)
    if (x.Article.Title != "trash")
        filtered.append(x);

Now you're hosed: you're stuck with n+1 queries, and there's no hope for the ORM to avoid that.  In many (imperative) programming languages, you'd be lucky for the code to show up in the former form; it'll more typically be in the latter form.

Challenge #2: Static analysis of code

Let's go back to your original example:

var filtered = scores.Where(x => x.Article.Title != "trash").ToList();

How can the ORM transform this into a single SQL query?  To do that, it would have to do non-trivial static analysis of the source code.  This can't be handled just through a simple library.

From the ORM's perspective, it is passed a function that determines which articles should be kept; it knows nothing about what the function does -- it can just call the function.  That's not enough to do the transformation you want.  To do the transformation you want, one would have to inspect the code of that function and figure out what it is doing and then somehow turn that into a SQL query.  That is decidedly non-trivial (and might require both compiler support and non-trivial static analysis algorithm).

Put another way, from the ORM's perspective, the above code is equivalent to

var filtered = scores.Where(f).ToList();

where the ORM knows nothing about what f does; all the ORM can do is invoke f on values of its choice.  When you don't know what f does, there's no way to transform that into a single SQL query.

Fixing this would require a way to take code written in the underlying language and compile it to SQL.  That basically means building a second compiler for the underlying programming language, and it's not easy.

In some languages, the ORM library actually obtains more than just a black-box function f: by using support for domain-specific languages or reflection, the ORM library might be able to obtain a parse tree for f.  In this case, the ORM library has more to work with, and in principle the ORM library could use static analysis of the parse tree of f to try to compile it to a single SQL query.  It will be language-dependent whether an ORM library can do this, purely as a library, without compiler support.  So in some languages achieving what you want will be easier than in others.


The hardness of solving $x^2=2$ What's the hardness of the following problem: $\textbf{argmin}_x\{|x^2-2|\}$.

By analytical calculation, I know the solution is $\pm \sqrt{2}$. But I am quite confused about whether it is hard with regarding to  its computation complexity.

What's the hardness of the following problem: $\textbf{argmin}_x\{|x^2-2|\}$.

It is $O(1)$. There is a single answer: $x = \sqrt{2}$. That means that, regardless of how that answer is represented, a computer can just output the answer and it solves your problem.

In general, to consider the hardness or complexity of a problem, you need there to be at least one variable as input; in particular, you need infinitely many possible input values. Otherwise, every problem can be solved trivially by just outputting the answer.


Is the language of TMs that decide some language Turing-recognizable? Is the language

$\qquad L=\{ \langle \text{M} \rangle \; | \; \text{M is a Turing machine that decides some language} \}$

a Turing-recognizable language? I think it's not,  as, even if I am able to tell somehow that a Turing machine halts for some input there are still infinite strings to check for. Similarly I think that this problem is not even co-recognizable. Am I right? If yes is there a more precise proof ?

Of course, this depends on what you exactly mean.

Do you mean, all the machines that decides a specific language? e.g.,
$$ L = \{ \langle M \rangle \mid M \text{ decides the language } A\}$$

then, it depends on the language $A$. For instance, if $A=HP$, the halting problem, then $L$ is clearly decidable (i.e., it is empty).

But if you mean, any language, i.e., that $M$ is a decider,
 $$ L = \{ \langle M \rangle \mid M \text{ halts on all inputs } \}$$
then $L$ is not recognizable, see Yuval's answer.


Explaining the difference between computer science and computer literacy What is a good metaphor or example to explain to an English major the difference between classical computer science and "being good with using MS-Windows"

computer science
computer programming
using computers

3 profoundly different things.   Most people have no idea what Computer Science even is.  They just see the word "computer". Hence, "he is a Computer Science major" can be interpreted as "He can hook up my printer".  Or that he's "good with computers". Even fewer people know the difference between computer programming and Computer Science.

Computer Science is computing theory.  CS can be learned without actual computers.   CPU micro architecture.  How to sort numbers, how to traverse lists, etc.  State machines.  Algorithms, big(Oh), etc.  How to design a programming language or compiler.

Programming is writing code and creating applications in a language and compiler created by a computer scientist.

Lastly, there is using a computer (using a GUI, mouse, and keyboard.  Internet, MS-Office, etc)

Yet all three of these are used interchangeably by laymen.

What is a good metaphor or example to explain to an English major the difference between classical computer science and "being good with using MS-Windows"   Or simply, a pithy example of how real computer science has nothing to do with using MS-Windows.

How about an automotive analogy?

uses computers and maybe "is good with computers" :: a driver (can drive and refuel safely) and maybe a car enthusiast (can jump start a car; is familiar with many makes and models; knows techniques like using windshield treatment to keep rain from reducing visibility).
programmer :: an automotive mechanic or technician. Knows how cars work. Can repair and modify cars and even build kit cars. Ought to know how to debug/diagnose problems by using the scientific method. Might not be aware of relevant theory and thus might write O(n2) loops.
software engineer :: an automotive engineer. Designs cars, engines, and other components that you can entrust your life with, and does it within schedule, cost, manufacturability, and other constraints. Knows how to apply the relevant theory/math such as finite element analysis.
computer scientist :: an automotive scientist. Researches new ideas in vehicles, human-machine interfaces, and propulsion. Does computational crash test modeling. Adds to the body of theory and experimental results.

So for people who equate all “computing” with “proficient in using some software package,” that's like equating driving proficiency with the ability to design antilock brakes that we trust lives to, that are manufacturable with consistent high quality and low cost, and work for years in extreme weather. Or equating driving proficiency with researching what kind of radar-triggered braking features will avoid collisions without freaking the driver into swerving into another lane.

Perhaps lay people confuse these terms because "computer science" classes teach computer use skills, programming, theory, or engineering. All that stuff (arguably not the first part) fits in the curriculum of computer science. None of it is the end-all "content" of computer science, just as English classes are learning on the way to an English major (a fuzzier concept).


Do system calls always means a context switch? When a system call takes place some kernel code must be executed. If some kernel code is being executed it means it can alter register values. So before this code gets executed the old process state must be saved. This is called context switch.
Now Wikipedia says that not all system calls need context switch. How is this possible?

A system call does not necessarily require a context switch in general, but rather a privilege switch. This is because the kernel memory is mapped in each process memory. The user process cannot access the kernel's memory because the memory mapping indicates which part are for the user and which parts are for the system. Thus a system call is really just a change of privilege, not of process. On some systems, like micro-kernels, a system call may involve a context switch because drivers are in a different process. But on monolithic systems like Linux this is not necessary. Linux also supports what is called the vDSO to implement some system calls entirely in userspace.

EDIT: attached a picture


Are there deterministic and/or non-interactive zero-knowledge proofs? The Wikipedia page on zero-knowledge proof says

  Zero-knowledge proofs are not proofs in the mathematical sense of the term because there is some small probability, the soundness error, that a cheating prover will be able to convince the verifier of a false statement. In other words, zero-knowledge proofs are probabilistic "proofs" rather than deterministic proofs. However, there are techniques to decrease the soundness error to negligibly small values.

Is it possible to prove that no zero-knowledge proof can be deterministic? What about non-interactive?

Goldreich and Oren, in their paper Definitions and properties of zero-knowledge proof systems, show that if the verifier is deterministic then interactive proofs trivialize to RP, whereas if the prover is deterministic then interactive proofs trivialize to BPP. See Section 4 of their paper.

Blum, de Santis, Micali and Persiano constructed noninteractive zero-knowledge proofs in their classic work Noninteractive zero-knowledge. The two parties do have to agree on a random key beforehand. Noninteractive zero-knowledge proofs have found many applications, for example to cryptocurrencies.  See Wikipedia for many references.


if A is decidable then B is decidable too Assume that a language A is reducible to language B. The claim is true?

if A is decidable then B is decidable too.

The correct answer is:

  This claim is wrong. If A is e.g. the empty language (which is clearly decidable) and B is $A_{TM}$, then surely ∅ is reducible to $A_{TM}$, but $A_{TM}$ is undecidable. The claim is true the other way round: If B is decidable then A is decidable too.

I have problem to understand two points:

A is e.g. the empty language (which is clearly decidable)

Why empty language is ("clearly") decidable and $L_∅$ is not?, where,  $$L_\emptyset = \{\langle M\rangle \mid M \text{ is a Turing Machine and }L(M)=\emptyset\}.$$

**A is reducible to $A_{TM}$ **

I have difficulties to image a reduction from $∅$ to $A_{TM}$, where $A_{TM} = \{<M,w> | \ M \ is \ a \ TM \ and \ M \ accepts \ w\}$

By definition, a language $L$ is decidable if there exists a TM $M\mid L = L(M)$ deciding it. Consider a TM that rejects on all inputs (for example, one where $q_o = q_{\text{rej}}$). The language of this TM is $\emptyset$, so $L=\emptyset$ is decidable.
With reductions, in general if $A\leq B$ ($A$ reduces to $B$), then $B$ is at least as hard as $A$ with respect to decidability. An undecidable language $A_{TM}$, regardless of what it actually is, is harder to decide than the decidable language $\emptyset$ by definition. The specifics of the reduction don't matter; the only information we needed was given in the problem statement (that $A$ is reducible to $B$).


What is the standard way to choose a new leader in Multi-Paxos? If you are unfamiliar with multi-Paxos or paxos, the following link might be a good refresher on it:

http://amberonrails.com/paxosmulti-paxos-algorithm/

or the paper by Leslie Lamport:

http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf

I was thinking about multi-Paxos and what one should do to elect a new leader if one is to fail (or in general, just if we want to re-elect a leader). I know that Multi-Paxos normally operates under the assumption that there is a stable leader. However, it does not mean that the Leader never fails or that we might never want to change the leader. It might be uncommon, but we must do something so that the system can function properly in the case that we might want to change leader.

I was wondering, what was the standard way to handle leader failures in multi-Paxos?

I have thought of different ways to handle failures of leaders and also google them, but it's still not clear to me how it should be done.

Let me also clarify what I mean by multi-Paxos and clarify that its not the mechanism described in the following source:

http://www.ict.kth.se/courses/ID2203/material/Lecture_11._Sequence_Consensus.pdf

What I mean by multi-Paxos is the abstract idea of deciding a list of Paxos instances by a single leader. This leader sends a range of Paxos Instances it wants to prepare and thus, it can hear a single a single prepare acknowledgement for the whole range instead of one per Paxos instances. Therefore, we can avoid a round-trip and have a more efficient prepare phase. Furthermore, we can now send accept messages immediately for that range since we have already prepared the values.

However, I was a little unsure of how multi-Paxos normally handled choosing a new leader, if the current leader happened to die. Does it doing by running a Paxos instance? Also, how often does it change leader? Can we do a leasing mechanism that after some time t a leader is re-elected? If we do, can this only be achieved if one assumes clock synchronization? The article I initially posted talks about multi-Paxos but kind of skips the detail I am trying to address.

If anyone has better sources or an idea of how one should implement leader election, I would love to hear about it, because I am sure that implementing multi-Paxos is not a "new" problem and that is has been addressed before at some point (and I would rather avoid very very weird "ad-hoc" ideas...)

Using the terminology of the Leslie Lamport Paxos Made Simple a leader is implicitly chosen when phase 1 is executed and a node hears it has the highest proposal. The problem is not leader election as phase 1 is leader election; the trick is that any server can start and win a new election before the previous leader can make any progress. So rather than the challenge of getting a leader the challenge is not getting too many competing leaders duelling; yet not waiting too long before attempting to get a new leader.  See this answer that quotes where the original Paxos papers talk about having a stable leader after a proposal has been accepted.

The raft paper has a lot of detail about leader timeouts. Basically you should have the leader send heartbeats. These can be no-op values as described in the Paxos Made Simple paper. If a follower does not get a message for a while it can timeout and propose. You add a bit of randomness to the timeout to try to prevent simultaneous proposers. You should respond with nacks as mentioned in the Papxs paper stating the higher promise value. That way if you do get simultaneously proposers the nacks will suppress candidates as only one candidate will get the highest number to a majority leading to nacks to the other candidates inside of one full round of phase 1+2 messages to the winner.

If servers stay up after the failure and the network stays stable a new leader should emerge promptly without too much delay or wasted messages on failed rounds due to duelling. The exact timeouts to set can be tuned to a given environment exactly as described in the raft paper.


What are the hardest problems that are in P if and only if P=NP? I used to think that NP complete problems are the "hardest" problems of all problems that would still be in P if P=NP. Now I think otherwise. What I'm asking is if there are any problems that are proved (/believed/maybe) to be harder than NP-Complete if $P\neq NP$, but are certainly in P if $P=NP$.

I was thinking of the sequence

$x_0 = P$

$x_{n+1} = $"All problems that have a checking algorithm in $x_n$"

e.g. $x_1 = NP$

If $P=NP$, then $x_n = P$ for all $n$. But if $P\neq NP$ is then $x_{n+1}$ different from $x_n$ for all $n$? Is this an ever continuing sequence so that there is no "hardest problem that meets the criteria" (because there would always be a harder one), or does this also hold for $x_\infty$ and would that be the hardest problem that meets the criteria? Or are there even harder such problems?

Well, here is a trivial example of a problem.

Inputs: a program P, an input x
Desired output: if P=NP, output "sweet!", else if P halts on x output "halts", else output "doesn't halt"

If P=NP, then this problem is in P.  If P$\ne$NP, then this problem is very hard (it's undecidable).

I realize this might not be what you're looking for; if so, perhaps it illustrates just how tricky it is to specify properties of this sort.


How can i fill shelves with products so that I have the maximum amount of sales? I have to do a project where I write a greedy algorithm to maximize a company's sales. There are 6 shelves, each with 8m length. I have to position 100 items whose length, value and max sales possibility I know on those shelves. My problem is, according to my instructions the max sales possibility changes according to the shelf height and the product's position on the shelf. More specifically, it says that the product position at the beginning of the shelf have a max sales possibility that is 30% reduced from those at the end, that the max sales possibility appears at the 4rth shelf and the highest and lowest have 30% of the max.
I would really appreciate any help you can give me as my background is not on computer science and I'm pretty lost. I've tried searching for information on bin packing problems but I haven't found anything that matches.

You'd need to give an exact specification of the problem, but we can do something. It sounds that every item can in principle be placed anywhere, but has a different value depending on where it is placed. It's not quite clear how "value" and "max sales possibility" interact, that's for you to figure out.

I'd try to find a "profit" per item, which will depend on its shelf location. What's even more important is "profit per meter". Since the profit changes by the same percentage for all items, you want to put all items with "high profit per meter" to positions where their profit isn't removed.

A "greedy" algorithm would start by sorting all items by profit per meter. Then you put the items sorted by profit per meter into the high-value places first. That gives you a decent solution.

You will have unused space left, so you will try to improve things by putting items there that fit better. Say you had a meter high value space and put a 60cm item there and don't have anything to use the leftover 40cm, then maybe placing a 100cm item would be better. That's reasonably similar to bin packing.

You can be pretty sure that the problem is NP-complete, which means in layman's terms that neither you nor anyone else will be able to find an optimal solution in reasonable time, so you try to find a good solution instead.


What is the relationship/difference between best/worse/expected case and big O/omega/theta? In the big O section of Cracking the Coding Interview 6th edition, I read the following.

"Best, worse, and expected case describe the big O for expected inputs and scenarios."

"Big O, big omega, big theta describe the upper, lower and tighter bounds for the run-time."

I understand what best, worse,  and the expected case is describing.

I know what bounds are but still don't understand the decoupling of the two concepts. Why would an algorithm have different bounds if the inputs/scenarios are the same?

Thanks in advance!

Why would an algorithm have different bounds if the inputs/scenarios are the same?

A deterministic algorithm has a single running time on each input. However, this is not what best case, worst case and average case are about. Let us consider a deterministic sorting algorithm. Its running time on an array of length $n$ depends on the array (and on the algorithm).
The best case running time is the minimal running time of the algorithm on an array of length $n$. The worst case running time is the maximal running time of the algorithm on an array of length $n$. The average case running time with respect to a distribution on arrays of length $n$ is the average running time of the algorithm on an array chosen at random from the given distribution.

For a randomized algorithm, it makes sense to consider the best case, worst case and average case for a single input, but this is not what these terms usually refer to.

  "Best, worse, and expected case describe the big O for expected inputs and scenarios."

This is simply wrong. I have explained above the meaning of best case, worst case and average case running time for the particular case of sorting algorithms, and the general case is similar.

How is running time measured? One way to measure running time is via an experiment – choose an actual machine, code the algorithm in a particular way, and measure the running time. However, this approach is problematic – which machine should we run the code on? How should we implement the algorithm? Another problem that the exact formula for the running time might be very complicated, and so not very helpful.

The way out is to state the running time up to a constant factor. This makes sense since under reasonable assumptions, the exact machine used and the exact implementation only affect the running time by a constant factor. Moreover, this allows us to hide the complexities of the exact running time by sweeping them under the rug of asymptotic notation.
(As an aside, we measure the running time on an abstract machine known as the RAM machine, which has unbounded memory. This allows us to make sense of arbitrary input sizes.)

Consequently, we always quote the running time in asymptotic notation. It is common to use big O notation, but this is in fact only an upper bound on the running time. Merge sort, for example, runs in time $O(n^5)$. It also runs in time $O(n\log n)$, and this upper bound is tight, in the sense that the worst case running time is $\Theta(n\log n)$.
When quoting the running time as $O(f(n))$, what one usually means is that the worst case running time is $\Theta(f(n))$. The reason we use big O rather than big $\Theta$ is that on some inputs the algorithm may run faster, and so for arbitrary inputs it may not be correct that the running time is $\Theta(f(n))$, but it is always correct that the running time is upper-bounded by $O(f(n))$.

  "Big O, big omega, big theta describe the upper, lower and tighter bounds for the run-time."

Big O, big $\Omega$ and big $\Theta$ are general-purpose asymptotic notation. They can be used to express asymptotic estimates on the rate of growth of arbitrary functions. Even in computer science, it is common to use asymptotic notation not only to measure running time, but also to measure memory consumption; and in other fields asymptotic notation is used for functions not related to algorithms at all.


What are some uses of the Thue-Morse sequence in computer science? Note: I come from a mathematics background.

The Thue-Morse sequence $t_n$ is a binary sequence that takes the value $0$ at the positive integer $n$ if the number of $1$s in its binary expansion is even, $1$ otherwise.

A definition that is closer to computer science states that $t_n$ is the binary sequence obtained by starting with $0$ and successively appending the boolean complement of the sequence obtained so far.

Thus, $t_n$ begins $0,1,1,0,1,0,0,1,\ldots$

This sequence is of much interest in mathematics, but so far I have not come across any applications in computer science. This surprises me, for the two following reasons:

The Thue-Morse sequence is automatic, i.e., the sequence is fully characterized by a finite automaton,
It is a binary sequence.

  What theoretic or practical applications of the Thue-Morse sequence are there in computer science?

I don't know if this counts as an application but at least it shows up. When using a polynomial rolling hash, it's tempting to do it modulo $2^{32}$ or $2^{64}$ (depending on the word size of the computer) since on most modern architectures addition and multiplication of integers just handle overflows this way, saving time. This method will fail often on Thue-Morse-like strings (like ABBABAAB...), as explained here. I remember not understanding the factorization of $T$ a few years ago, the key is the recurrence relation $t_{2n} = t_n$, $t_{2n+1} = 1-t_n$

Alternative explanation of the factorization: from the "append the negated sequence" definition one can directly see $\Pi_n (1-x^{2^n})$ , since each each term does exactly that.


An algorithm to detect if the conversion rate growth acceleration rate is still rising or stopped An example.

I have bought a currency while the rate was 1.0. As soon as the conversion rate has increased to 2.0 I would like to sell the currency. Now, that would be an easy task to do. But we are not searching for "easy" tasks, are we?

What if there was a way to determine, whether the rate is still growing or not? For example, what if the conversion rate was still growing at +0.5 per minute, in that case - I would be able to sell the currency at rate 3.0 if only I have waited for 2 more minutes. Alternatively, I would be able to sell the currency at an even higher rate, if it was determined that the acceleration rate either stopped, or became negative.

Here is a visual representation of what I want to accomplish:

black line - good, but too early to sell
green line - sell now
red line - better sell it now, before rate decreased

Is there an algorithm to accomplish this task?

At this point - it is not clear to me:

What would be the best time range to take into acceleration rate calculations. Should I consider the rate change during the last 10 minutes, 5 minutes or 20 seconds?
How do I determine that the "growth" (acceleration rate) has stopped or is close to being stopped?
Do I only need to know only the conversion rate, or also number of trades (buys/sells) at a given time frame?

Any advices are appreciated.

You are seeking to predict future values of the time series based on past values.  There's lots in the area of time series analysis and prediction; I suggest reading about those topics.  The right approach will depend on domain knowledge and how currency rates tend to change and what statistical model is appropriate in your setting.


LL(k) Prediction Techniques (and Insight on method applied) I'm requesting references for LL(k) in situations where k > 1 for reasons described below.

I'm looking for research/notes/anything involving LL(k) predictions.

Any time I look up LL(k) I end up with the description starting about LL(k) and focusing on LL(k) where k = 1.

Is there a formal description for the process to predictions where k can be greater than one, sometimes even as high as 7 to 15?  Granted I can't vouch for or against the performance implications of the k being so high as that, but I just wanted to know if there's been any literature on the subject.

It turns out someone wrote half a book about LL(k) parsing, which wasn't mentioned on Wikipedia until I added it a coupe of minutes ago.

Parsing Theory: LR(k) and LL(k) Parsing by Seppo Sippu; Eljas Soisalon-Soininen (1990).

I've looked briefly through it and it does have LL(2) examples too.

EDIT: As rici says below, this is the 2nd volume of a two-book series by the same authors; the first volume in the series is titled Parsing Theory: Languages and Parsing (1988).

And you can obviously find some level of info on LL(k) in most compiler books, but Sippu and Soisalon-Soininen have the most extensive treatment I found of LL(k). More recent introductory textbooks generally punt the proofs on anything to do with LL(k) with to Sippu & Soisalon-Soininen's 2nd volume.

LL(∗) however is not covered by Sippu & Soisalon-Soininen (as far as I can tell), but that's probably understandable given the book's age. For LL(∗) the 2011 ANTLR PLDI paper is probably the best reading.


if $ b(x) <f(x) \leq g(x)$ where $b, g \in \Theta(x)$ can we state $f(x) \in \Theta(x)?$ I restate the question:
if $ b(x) <f(x) \leq g(x)$ where $b, g \in \Theta(x)$ can we state $f(x) \in \Theta(x)?$
notice that $b(x)< f(x)$ and not $b(x) \leq f(x)$.
In other words what if

$f(x) \in \omega(b(x)) $ and

$f(x) \in O(g(x))$

can we state $f(x) \in \Theta(x)$?

b(x) is between $c_1·x$ and $c_2·x$ if x is large. g (x) is between $d_1·x$ and $d_2·x$ if x is large. So f (x) is between $c_1·x$ and $d_2·x$ if x is large, which makes it $\Theta(x)$.


Can the semantics of a numeric hierarchy be faithfully represented in Haskell? I am trying to represent a fragment of a number hierarchy using the Haskell concepts of value, type, and type class. I would like the Haskell code to reflect the mathematical semantics $\vdash ((x \in \mathbb{N}) \land (\mathbb{N} \subset \mathbb{Z}\subset \mathbb{Q}) \Rightarrow (x  \in \mathbb{Q}))$. In words, given that the set $\mathbb{N}$ of natural numbers is a subset of the the set $\mathbb{Z}$ of integers and integers are a subset of rationals $\mathbb{Q}$, we can deduce that every natural number is an rational number. I omit the constraint that natural numbers are actually a proper subset of integers.

Below is my attempt at relating the math and Haskell semantics. I am unsure whether a class is a set of types as stated by GAST (Section 3.5) and hence a type can be considered as an element of a class $(T \in TC)$.

Note it is possible that $V_1=V_2$ (e.g. 1:Nat=1:Int)

Below is my flawed attempt to capture the mathematical meaning using Haskell.
I am aware that implementing rationals would lead to a situation where rationals were represented by both a type and a type class (not good!). Please note for research purposes I am restricted to only using values, types,and type class. I am not intentionally seeking to impose Object Oriented class semantic on Haskell.

data Natural = One | Suc Natural deriving Show
data Integers = Zero | Succ Integers deriving Show

class RationallNumbers x where
  plus::x -> x -> x

instance RationallNumbers Integers where
 plus  x  Zero = x
 plus  x  (Succ y)  = Succ (plus x  y)

instance RationallNumbers Natural where
 plus  x  One = Suc x
 plus  x  (Suc y)  = Suc (plus x  y)

twoPlusTwoNat = plus (Suc One)  (Suc One)
twoPlusTwoInt = plus (Succ (Succ Zero))  (Succ (Succ Zero))

To sum up my question is:

Can the numeric hierarchy described be represented in Haskell using the semantic concepts  of values, types, and classes?

Related questions: A mathematical (categorical) description of type classes, Is there a model theory for Haskell type classes?

Yes, it is definitely possible. However your approach is a good starter but keep in mind to have a functional approach on writing code in Haskell. You can create expressions so you can define and 'override' methods.

As a suggestion I will give a part of code of how such expressions can look like as values and types.

data Exp = Lit Value
         | Assign Name Exp
         | Variable Name
         | Apply Exp Exp
         | Assist Name Exp
         | Exp :+:  Exp
         | Exp :-:  Exp
         | Exp :*:  Exp
         | Exp :=:  Exp
         | Exp :==: Exp
         | Exp :/=: Exp
         | Exp :>:  Exp
         | Exp :>=: Exp
         | Exp :<:  Exp
         | Exp :<=: Exp
         | Exp :&&: Exp
         | Exp :||: Exp
         deriving (Show)

This is some code out of a language I've written for controlling micro-controllers. The evaluation can be done as following:

-------------------------------------------------
-- Evaluate Expressions Utilities
-------------------------------------------------
-- Evaluate Integer Arithmetic operations
evalInt :: KDLMap -> Exp -> Int
evalInt _ (Lit n)          =  kdlintToInt n
evalInt k (Variable n)     =  kdlintToInt $ searchVariable' n k
evalInt k (e :+: f)        =  evalInt k e + evalInt k f
evalInt k (e :*: f)        =  evalInt k e * evalInt k f
evalInt k (e :-: f)        =  evalInt k e - evalInt k f
evalInt _ _                =  Prelude.error "Unable to perform operation."

-- Evaluate Boolean operations with Integers
evalIntBool :: KDLMap -> Exp -> Bool
evalIntBool k (e :<:   f)         =  evalInt k e <  evalInt k f
evalIntBool k (e :>:   f)         =  evalInt k e >  evalInt k f
evalIntBool k (e :<=:  f)         =  evalInt k e <= evalInt k f
evalIntBool k (e :>=:  f)         =  evalInt k e >= evalInt k f
evalIntBool k (e :/=:  f)         =  evalInt k e /= evalInt k f
evalIntBool k (e :==:  f)         =  evalInt k e == evalInt k f
evalIntBool _ _            =  Prelude.error "Unable to perform operation."

-- Evaluate Boolean operations with Booleans
evalBool :: KDLMap -> Exp -> Bool
evalBool _ (Lit n)         =  kdlboolToBool n
evalBool k (Variable n)    =  kdlboolToBool $ searchVariable' n k
evalBool k (e :&&: f)      =  evalBool k e && evalBool k f
evalBool k (e :||: f)      =  evalBool k e || evalBool k f
evalBool _  _              =  Prelude.error "Unable to perform operation."

For more information, hit me up. I will provide it on my github quite soon, so you can see more. But to answer your question, yes it's definitely possible.


Help writing a dynamic programming algorithm in English It’s Friday night and you have $n$ parties to go to. Party $i$ has a start time $s_i$ end time $t_i$ and a value $v_i \ge 0$. Think of the value as an indicator of how excited you are about that party. You want to pick a subset of the parties to attend so that you get maximum total value. The only constraint is that in order to get a value $v_i$ from party $i$ you need to attend the party from start to finish. Hence you cannot drop in midway and leave before the party ends. This means that if two parties overlap, you can only attend one of them. For example, if party 1 has a start time of 7pm and ends at 9pm and party 2 starts at 7:30pm and ends at 10pm, you can only attend one of them. On the other hand, if party 2 starts at 9pm or later then you can attend both. Given as input start times, end times and values of each of the n parties, design an $O(n \log n)$ time algorithm to plan your night optimally. Describe in English the idea of your algorithm. If you use dynamic programming define the memo table, base case and recursive steps. You don’t need to write the pseudo code or provide a proof of correctness.

I am having difficulty beginning this problem. My initial thought was to have the base case be to choose the value with the initial start time and the greatest $v_i$, however if party $i$ runs for your entire start to end time, you might not maximize $v_i$. I would greatly appreciate some insight into how to do this problem.

Since this problem is a learning exercise of yours, I will just write the ordered subproblems used in dynamic programming. In general, I consider it is about more than half way through a nontrivial problem that can be solved by dynamic programming when the ordered subproblems have been specified clearly, at least in term of "difficult" thinking since the rest are more routine.

The subproblems are computing $v[i]$, the maximal total value you can get when you just finished party $P_i$. To help computing these subproblems, that is, from earlier subproblems to later subproblems, you may sort the parties by their ending times so that $P_1,P_2,\cdots,P_n$ end in order of time. After the sorting, $v[i]$ will only depend on those $v[j]$ where $j<i$ or, to be more precise, those $P_j$ whose ending time is before $P_i$'s starting time. (This condition can be made even more restrictive, which may be unnecessary for your exercise and which may be necessary to get a better grade.)  There are several more details such as the base case and the recurrence relation, which I will leave for you to fill in.


Is this relation in Boyce-Codd's Normal Form? I thought I understood BCFN until I bumped into this example from my course slides.

A relation in a library database contains what books are currently borrowed by what users.
The relation contains the unique ID of the user, their name and the title of the book.
Different users might share the same name.
A book can only be borrowed by one user.
A user can have borrowed more than one book.

An example of this relation could be:

USER_ID
USER_NAME
BOOK_TITLE

U012
Charles
Hamlet

U034
Alex
Blue Moon

U491
Diane
Capital

U034
Alex
The Crow

U491
Diane
Economics 2

U012
Charles
Lost Girl

U034
Alex
Chess basics

U012
Charles
Greek History

U491
Diane
Red Mars

According to the slide, this relation is in Boyce-Codd's Normal Form,as:

all functional dependencies of the form $\alpha \rightarrow \beta $
are either trivial or satisfy that $\alpha$ is a super-key of the
relation

While it is my understanding that those are the requirements for BCNF, I don't think this relation satisfies them. In particular, the functional dependency USER_ID $\rightarrow$ USER_NAME is not trivial (as $\beta$ is not a subset of $\alpha$) and $\alpha$ is not a super-key (since by itself we cannot distinguish between entries representing different books borrowed by the same user).
Am I missing something?

Assuming that each book has a different title, you are correct in thinking that the relation is not in BCNF.
In fact, the (only) candidate key of the relation is  Book_title, so the functional dependency User_id -> User_name violates the definition of BCNF. Assuming that a cover of the dependencies are:
User_id -> User_name    (each user_id identifies a user with a certain name)
Book_title -> User_id   (each book can be borrowed only by a certain user)

a decomposition of the original relation in BCNF is:
R1(User_id, User_name)  with candidate key User_id
R2(Book_title, User_id) with candidate key Book_title


Is it immediately true that the class of P is a subset of the class NP? Forgive me if this is a stupid question - it's been a while since I thought at all about complexity theory and I want to make sure that I have covered all the possible angles with regards to the basics.

My question is, is it immediately true that class P is a subset of the class NP? That is, do we need to prove that the set of problems for which a solution may be obtained in polynomial time, is a subset of the class of problems for which a potential solution may be verified in polynomial time?

For example, consider a problem has multiple solutions and suppose that at least one of these solutions can be found by a program that runs in polynomial time. Then this problem is clearly in the class of P, since a solution can be found in polynomial time.

However, this does not tell us that all solutions are verifyable in polynomial time. Could it not be the case that some other solution to the problem is very difficult to verify?

P problems are a subset of NP problems. For a problem to be in P it must be decidable in polynomial time. For a problem to be in NP, it must be verifiable in polynomial time. If a problem is decidable in polynomial time, it is clearly verifiable in polynomial time as it can simply be verified by deciding it a second time. Therefore, all P problems are in NP.

I think that the fundamental component that you may not be remembering is that P and NP refer to specific time complexity classes of decision problems. Decision problems can't return general solutions. They can return yes (accept), no (reject), or never return.


Is the certificate for primality testing polynomial in the length of the input? If we were to assume that primality testing was in NP.

What would the certificate be, so that a polynomial time verifier can check the number X is indeed prime?

Before it was proven that primality is in P, it was known that a complete factorisation if n-1 could be used to prove primality of n.  Now this also requires a proof that all factors in the claimed factorisation are actually themselves primes; this leads to a O(n^2) size certificate.

Google for “Pratt certificate”.

(When you use a certificate to solve a problem in NP, you cannot just “trust” the certificate. So if I tell you “here is a complete factorisation if n-1”, you can’t just believe that. You’d have to check that the product of the factors is actually n-1, which is easy. But you’d also have to check that each of the numbers that I claim are prime factors are actually prime, so you need a certificate for primality of these smaller numbers as well)..


What kind of reductions are usually used in order to prove PP-completeness? I've read that MAJSAT is PP-complete.  Under what type of reduction is this true? What kind of reductions are usually used in order to prove PP-completeness?

Here "PP-complete" means "complete for PP".  The definition of PP defines the complexity class PP; it does not define the type of reduction you can use, as that is an orthogonal concern.  So, "complete for PP" actually means "complete with respect to a particular class of reductions", and the meaning of that is implicitly parametrized by a class of reductions (usually the reader assumes you will be able to infer the class, from context).  For each class of reductions, you potentially get a different notion of completeness.

In this case, we're talking about polynomial-time many-one reductions, also known as Karp reductions -- the same class of reductions as is commonly used in the definition of NP-completeness.  This becomes immediately clear if you read the proof of completeness of MAJSAT (it's immediate to see that this is the type of reduction that gets constructed, in that proof).

In the future, please make sure to do research through standard sources before asking here, and to use some effort to formulate your question clearly and precisely -- that will increase the chances that you get a useful answer.


Randomized algorithm for 3SAT There is a very simple randomized algorithm that, given a 3SAT, produces an assignment satisfying at least 7/8 of the clauses (in expectation): choose a random assignment. A random assignment satisfies each clause with probability 7/8, and so linearity of expectation shows that the expected fraction of clauses satisfied by a random assignment is 7/8.

Can this be done in a deterministic way? If so, why are we interested in the randomized algorithm?

The random assignment algorithm can be derandomized (made deterministic) using the method of conditional expectations.

Let the 3SAT instance consist of clauses $C_1,\ldots,C_m$. During the algorithm we will assign values to variables. The score of a clause $C$ is defined as follows:

If $C$ is satisfied then its score is 1.
If $C$ is not satisfied and has $k$ unassigned literals then its score is $1-2^{-k}$.

Initially the score of each clause is $1-2^{-3} = 7/8$, and so the total score is $(7/8) m$. We now assign values to the variables $x_1,\ldots,x_n$ in order. Suppose that we have assigned values to variables $x_1,\ldots,x_{i-1}$, and the current total score is $S = S(C_1)+\cdots+S(C_m)$. Let $S_0,S_1$ the total score if we assign the values $0,1$ (respectively) to $x_i$. I claim that $S_0(C)+S_1(C) = 2S(C)$ for any clause $C$, and so $S_0 + S_1 = 2S$. Indeed:

If $C$ is satisfied (only given $x_1,\ldots,x_{i-1}$) or doesn't contain $x_i$ then $S_0(C) + S_1(C) = 2S(C)$.
Suppose that $C$ contains $k$ unassigned literals, including $x_i$. Then $S(C) = 1-2^{-k}$, $S_0(C) = 1-2^{-(k-1)}$, and $S_1(C) = 1$. Therefore
$$ S_0(C) + S_1(C) = [1 - 2 \cdot 2^{-k}] + 1 = 2(1 - 2^{-k}) = 2S(C). $$
A similar argument works when $C$ contains $\bar{x}_i$.

Since $S_0 + S_1 = 2S$, either $S_0 \geq S$ or $S_1 \geq S$ (possibly both). Therefore there is some assignment to $S$ such that after the assignment, the new score is at least $S$.

The initial score is $(7/8)m$ and the algorithm ensures that the score never decreases. At the end, the score of a clause $C$ is 1 if it is satisfied and $1-2^{-0}=0$ otherwise. Thus the final assignment satisfies at least $(7/8)m$ clauses.

Given that there is a deterministic algorithm, why are we interested in the randomized one? There are several reasons:

The randomized algorithm is much simpler.
The randomized algorithm is potentially faster.
The randomized algorithm can be converted to a deterministic one using the method of conditional expectations; we can think of it as a recipe for constructing a deterministic algorithm.

More generally, it is conjectured that every randomized polytime algorithm for a decision problem can be derandomized (this is the $\mathsf{P}=\mathsf{BPP}$ conjecture). Randomized algorithms will still be interesting for all the reasons enumerated above.


What to prove and how to prove it In learning about proof theory, I am interested to know how to go about "proving properties of a program". I don't exactly see yet what needs to be proven, nor how to prove it, which leads to this brief discussion followed by some questions.

In some languages (such as TLA+), the program is the specification (I think). If not TLA+, maybe you can do that in Coq, but I've heard of it. So that means roughly that what you write is automatically proven. But if that is the case, how do you prove that it's proven. It seems that at some point you have to actually test both the code and the proofs and see that it does what the specification says. Some basic TDD.

In reviewing the Curry-Howard correspondence, programs are proofs, or at least lambda/functional/logic style programs. Not really sure what this means in practice. If simply writing a new function that implements a specification means we have a proof, or what.

So the questions are:

What exactly we are proving.
How do we prove that the system meets the specification (if the language is or is not the actual specification). If I write code that says "I will always handle this HTTP request error by tracing its output to the console", and that is "specified" in the specification, then how does it get proven. Not sure what I do to say "guaranteed, this behavior will happen". In my head the only way this can be proven is by actually doing tests on the code (i.e. model testing or just brute force simulation testing like you would see in TDD).
When writing tests (as in TDD) comes into play when creating these proofs. Wondering if proofs need tests, sorta thing, or at what point you are done with your proof being proven.

So it seems that what we want to prove is that the system behaves as expected. And given we have defined how we want the system to work, the question is how to prove it matches the specification, at a high level. How much do we prove, how do we know the proofs actually prove what we want and the behavior will be what we want (and proven).

I think you raise an important point, which is that in a high level language, specifications can be hard to distinguish from implementations. For example, in Coq, the specification of "The sum of the elements of a list of naturals" is probably going to look something like:

Fixpoint sum (l : List Nat) : Nat :=
  match l with
   | [] => 0
   | x::xs => x + sum xs

It's hard to imagine what the specification of this would be, other than some predicate like

 Inductive Is_Sum : Nat -> List Nat -> Prop :=
    | IS_Empty : Is_Sum 0 []
    | IS_Cons : Is_Sum s xs -> Is_Sum (x + s) (x::xs)

which really just seems like a re-formulation in terms of logic programming. Indeed it is very easy to show forall l : List Nat, Is_Sum (sum l) l.

At this point, it is indeed possible to test the definition of sum and make sure it lines up with our intuition, e.g. check sum [1,2,3] = 6. However, there is an important other step we can check in terms of "specification checking", that of proving derived properties. For sum, we could prove

Proposition sum_append : forall l1 l2, sum (l1 ++ l2) = sum l1 + sum l2

or

Proposition sum_leq : forall l x, In x l -> x <= sum l

These propositions establish the consistency of our definition against some of our intuitions, and avoid certain silly mistakes, e.g. if we had returned $1$ instead of $0$ for the empty list.

Indeed, often for our purposes the properties we actually are interested are the derived properties! Defining the full specification is only a means to an end, like strengthening the induction hypothesis.

Finally, it's probably useful to note that in real life, our specifications are often much simpler than our implementations! Indeed, if our implementations are doing nothing clever, then why do we care so much about proving them correct? (well, actually even the simplest of programs might benefit from proofs.)

One rather simple example is merge sort which while pretty straight forward, is certainly complex enough to warrant a proof of correctness, and at any rate is very different looking than its specification.


Program that generates a regular expression from an FA Possible Duplicate:
  How to convert finite automata to regular expressions?

Im curious if anyone knows if its possible to write a program to generate a regular expression given a finite automation.

To make things less complicated I want to limit the number of states to about 4, assume the FA is in minimal form and that the FA has only one FinalState and only one StartState.

Ive been thinking about it for a while now and I think the first obvious thing to do would be to create a transition table for the FA.

So an FA could look like this:

NumberOfStates 4
StartState   1
FinalState   4
StateNumber  NextStateA   NextStateB
1            2            4
2            3            2
3            4            4

And would generate the regular expression: b + (ab*a(a + b))

Ive been racking my brain for hours but am stumped on how to go about this. Any ideas is greatly appreciated.

Here's one resource on the matter:
www.cs.dartmouth.edu/~ac/Teach/CS39.../lec09dfa2regexp.pdf

There's a commonly known Dynamic Programming algorithm which can do it. The link I send outlines the algorithm, though it doesn't convert to code. The DP algorithm is pretty common (I think it's usually used in the proof that DFA and RE are equivalent) so if you're looking for the code, it's probably out there somewhere.


Can Depth-first search (DFS) with alphabetical traversal of neighbors be run in O(|V|+|E|) time? I feel like the answer is no but I'm not sure. I think it's commonly accepted that DFS runs in $O(|V| + |E|)$ time. I've read a few explanations and they all make sense if the neighbour traversal for any given vertex can be done in arbitrary order.

But I've noticed a commonly suggested DFS behavior is to traverse the neighbors in alphabetical order (i.e. CLRS exercise 22.3-2), and I don't see how this can be done in $O(|V|+|E|)$ time. This became evident to me when actually trying to implement this in runnable code.

I see two ways to do it:

I can keep the list of vertices and each vertex's adjacency list sorted as I'm constructing the graph. However this means $O(V)$ insertion time for each new vertex in the graph, which means a total of $O(|V|^2)$ insertion time over $|V|$ nodes. And $O(|E'|)$ insertion time for a new edge where $|E'|$ is the number of neighbours in a particular vertex's adjacency list, meaning $O(|E'|^2)$ time to construct the adjacency list for any given vertex.

OR

Construct the graph and insert the vertices and adjacency elements in arbitrary order, but then sort them before running DFS. But comparison-based sorts are $\Omega(n\log n)$ so I'd have $O(|V|\log|V|)$ sort time for the list of vertices, and $O(|E'|\log|E'|)$ for each adjacency list.

In either case it doesn't seem like the runtime is $O(|V| + |E|)$ any more. Can someone confirm or refute? Thanks.

No, there is no linear time algorithm (for worst case).

Note for a list of $n$ positive integers, you can construct a tree with a root and $n$ children encoded by these integers respectively and traverse this tree in alphabetical order to sort these integers. So your problem is at least as hard as sorting.


Complexity of computing matrix powers I am interested in calculating the $n$'th power of a $n\times n$ matrix $A$. Suppose we have an algorithm for matrix multiplication which runs in $\mathcal{O}(M(n))$ time. Then, one can easily calculate $A^n$ in $\mathcal{O}(M(n)\log(n))$ time. Is it possible to solve this problem in lesser time complexity?

Matrix entries can, in general, be from a semiring but you can assume additional structure if it helps.

Note: I understand that in general computing $A^m$ in $o(M(n)\log(m))$ time would give a $o(\log m)$ algorithm for exponentiation. But, a number of interesting problems reduce to the special case of matrix exponentiation where m=$\mathcal O(n)$, and I was not able to prove the same about this simpler problem.

If the matrix is diagonalizable then taking the $n$th power can be done in time
$$O(D(n)+ n\log n)$$
where $D(n)$ is the time to diagonalize $A$.

Just to complete the details, if $A=P^{-1}DP$ with a diagonal $D$, then
$$A^n = (P^{-1}DP)^n = P^{-1}D^nP$$

and $D^n$ can be computed by just taking each element of the diagonal (each eigenvalue of $A$) to the $n$th power.


Regular expression for containing 010 as a subword I am studying for a test in computer science, and am encountering difficulties with regular expression. Here is example of a question I don't understand.

I managed to solve the following question:

  Give a regular expression for the language of all words over $\{a,b\}$ which contains one of $aa,bb$ as a subword.

My solution:
$$(a ∪ b)^*(aa ∪ bb)^*(a ∪ b)^*.$$

I am having trouble with the following question:

  Give a regular expression for the language of all words over $\{0,1\}$ which contains $010$ as a subword.

In the first one, L1 = (a+b)*(aa+bb)(a+b)* not (a+b)(aa+bb)(a+b)* because in the second one, it is possible only to have one character of a or b and then we have to find the occurrence we need. Your L1 denies any word that does start with (aa+bb). It also forces all the words to start with a or b.

By the way, I use + for | and ∪.

So for the second one, it is in the same manner:

L1 = (0+1)*(010)(0+1)*

010 might occurs in the beginning, the middle or the end of the word.


Handling dead state in NFA to DFA conversion I want to convert below NFA into DFA:

I prepared below tables and finally the NFA:

NFA

However I feel I am wrong here, since original NFA does not have any transitions defined for state C and my final DFA does not have any dead state. However I dont understand where I am going wrong.

Your DFA actually looks correct. Why do you need a dead state?

A dead state means the automaton was given a prefix of an input that will never lead to an accepting state. But the language of the NFA has no such prefixes - whatever the prefix is, if you add "10" or "11" you will get  to an accepting state.

Anyways, the right thing to do now is to verify that the DFA works fine for several sample inputs. More generally, to prove it actually does decide the language generated by $(0+1)^*1(0+1)$.


Why are pushdown automata countable? I began a chapter in a textbook on computational theory where they begin to talk about decidable languages.

The problems in this section are pretty confusing and I honestly don't know how to begin them because I'm not 100% on what they mean when they say "countable".

Can anyone help walk me through this problem in the book, that simply states;

  Show that the number of push-down automatons is countable.

Since you don't provide any attempt on your own part, note two things.

The definition of countability.

  A set $A$ is countable if and only if $A$ is finite or there is a bijection $f : A \to \mathbb{N}$.

How do you represent pushdown automata in a formal way?

If you digest the first item and answer the second, the answer should become apparent.


Is there any implementation of AO* algorithm? I'm trying to solve And-Or Graph, and I find AO* algorithm can handle it. Someone said it's already used in AI, but I can't find it in detail.

Have it implemented? Or it's just a pseudocode that can't realized? If it exists, where can I find it? Or any suggestions to help me to implement it? I'm really appreciate your help.

I cannot point you towards an existing implementation, but I am pretty confident that it is not too hard to implement yourself. I suggest you to have a look at this paper by Nau, Kumar and Kanal, which has detailed pseudocode for AO* and other related algorithms such as A* and branch and bound. In particular, have a look into Section 7 of that paper and the procedures they call P8 and P9.


Equisatisfiability in the reduction from 4-SAT to 3-SAT So If I understood correctly, the conversion from 4-SAT statement to 3-SAT statement follows the following approach:

(a or b or c or d) -> (a or b or z) and (-z or c or d)

Where the z is a new literal. However, with 4 literals there exists 4^2 different permutations (a or b or c or d) and (-a or b or c or d) and (a or -b or...) and ...

If I convert each of the clauses with the approach above (add always new literal z_n and it's negation) like:

(a or b or z) and (c or d or -z) and (-a or b or z_2) and (c or d or -z_2) and ...

, then the resulting 3-SAT statement is indeed satisfiable. Even if the 4-SAT statement with the all permutations for 4 literals is not. They should be equisatisfiable?

You're right in saying that they should be equisatisfiable. And they are.

I'm not sure why you think converting your unsatisfiable $4-\text{SAT}$ instance into a $3-\text{SAT}$ instance would make it satisfiable. Because it doesn't.

If a $4-\text{SAT}$ instance is unsatisfiable, then no matter how you choose to assign truth values to your variables, there will be some clause that is not satisfied. Without loss of generality, let that clause be $(a \vee b\vee c\vee d)$. Since this clause is not satisfied by your assignment, it follows that all of $a, b, c$ and $d$ are false.

Now converting this into a $3-\text{SAT}$ instance gives you these pair of clauses: $(a \vee b \vee z)(\neg z \vee c\vee d)$. Note that since $a, b, c$ and $d$ are all false, in order for both of these clauses to be satisfied, both $z$ and $\neg z$ need to be true, which is impossible.

In other words, the resulting $3-\text{SAT}$ instance is also unsatisfiable.


What happens to the running time of an $O(n \ln n)$ algorithm if you double $n$? Problem:
Suppose the running time of a certain algorithm is $O(n \ln n)$. We happens to the running
time of the algorithm if $n$ doubles.
Answer:
Let $R_1$ be the running time of the algorithm when the input is of size $n$. Let $R_2$ be the running time of the algorithm when the input is of size $2n$. Let $R = R_2 / R_1$.
\begin{align*}
R &= \frac{ 2n \ln (2n)}{ n \ln n } =  \frac{ 2 \ln (2n)}{ \ln n } \\
R &= \frac{ 2 ( \ln(2) + \ln(n))}{ \ln n } =
    \frac{ 2 ( \ln(2) )}{ \ln n } + \frac{ 2 ( \ln(n))}{ \ln n }\\
R &= \frac{2 \ln(2)}{ \ln n } + 2 \\
\end{align*}
This does not seem right to me. Is it? If it is wrong, where did I go wrong?

I  suggest following property: if for functions $g,f \gt 0$ we have $f \sim kg$, for some constant $k\gt 0$  i.e. $\lim\limits_{n \to \infty}\frac{f(n)}{g(n)}=k$ and both, $g$ and $f$, have not zero as limit point, then $O(f)=O(g)$.
Proof:
Let's consider $\phi \in  O(f)$, then we have $\phi \leqslant C f \leqslant C (k+\varepsilon)g$ for appropriate $C, \varepsilon$ and $n \gt N.$ So $O(f) \subset O(g)$. Using, that we have also $\lim\limits_{n \to \infty}\frac{g(n)}{f(n)}=\frac{1}{k} \gt 0$, we obtain reverse including.
Based on brought property we can say, that running time $O(n \ln n)$ does not change if we double $n$:
$$O(n \ln n) = O(2n \ln 2n)$$