Alternative graph data structures Are there any graph implementation data structures beyond the standard adjacency list/matrix ones? If so, what are they?

I welcome experimental ones as well as highly specialized ones.

A little background: I'm developing an algorithm that relies heavily on graph operations, so I'm doing research in graph implementation. I'm not looking for out-of-the-box solution, but rather for additional material in hope to combine my findings into something that will optimize my algorithm.

An adjacency matrix is not suitable for me in its core form, because it is costly to resize. In my environment, vertices are expected to be frequently added/removed.

An adjacency list is a bit better approach. Yet, it lacks the ability to efficiently cross-reference information from different nodes. Further, the graph is weighted, so I need immediate neighbors sorted for a fast search. However, the weights are also dynamic: they change frequently (are explicitly updated) and decay with time (change implicitly based on the type/time of the last operation).

The graph is expected to have somewhere between 50 and 100 vertices. Once a new vertex is added, it will form edges with some or all of the other vertices, depending on its life time.

I've tried using sorted lists, but still haven't found any efficient way to accommodate all the criteria listed above.
I also considered hash-tables, similar to the answer below, but they don't solve the problem with sorting.

Here are some examples of slightly different approaches:

Hash-table

Key into hash-table is a vertex, value is a list of vertices it is connected to, the edge is thus a relation between the key and the element of the value in the hash-table.  This is not so different from adjacency list except that testing for presence of the vertex will be faster, but it will take more spece to store the graph.

This, obviously, describes a directed graph.  You could include the reversed edges to make it work as undirected graph.

Example (JavaScript):

function graph() {
    var vertices = {}, g = { vertices: vertices };
    g.getVertex = function (vertex) {
        return vertices[vertex];
    };
    g.getEdge = function (from, to) {
        var adjacent = vertices[from], result;
        if (adjacent.indexOf(to) > -1) result = [from, to];
        return result;
    };
    g.addEdge = function (from, to) {
        var edges = vertices[from] || [];
        edges.push(to);
        vertices[from] = edges;
    };
    [].slice.call(arguments).forEach(function (edge) {
        g.addEdge.apply(g, edge);
    });
    return g;
}
graph([1, 2], [1, 3], [2, 1], [2, 3], [3, 5], [3, 6], [3, 4],
      [4, 7], [5, 2], [5, 6], [6, 3], [6, 7]);
// { vertices:
//    { '1': [ 2, 3 ],
//      '2': [ 1, 3 ],
//      '3': [ 5, 6, 4 ],
//      '4': [ 7 ],
//      '5': [ 2, 6 ],
//      '6': [ 3, 7 ] },
//   getVertex: [Function],
//   getEdge: [Function],
//   addEdge: [Function] }

Graph-proper data structure

We define vertex as a tuple of the value and a list of edges from this vertex to other vertices it is directly connected to.  This is a little bit more compact than the hash-table, but testing whether vertex is in a graph becomes linear (just as in adjacency list / matrix).  Same as before we can add edges in the opposite direction to make this graph undirected.  This is different from adjacency list in that retrieving all adjacent vertices to a given vertex is a constant time operation, while in the list it is linear in time.  Adjacency matrix would also give constant time for this, but will use more space, especially if a graph is sparse.

Example (Prolog):

:- use_module(library(record)).

:- record vertex(value, arcs=[_ | _]).

lookup(X, [X | _]).
lookup(X, [Y | Xs]) :- X \== Y, lookup(X, Xs).

instantiated(Goal, [X | _], []) :- \+ call(Goal, X).
instantiated(Goal, [X | Xs], [X | Ys]) :- call(Goal, X), instantiated(Goal, Xs, Ys).

vertex_instantiated(Vertex) :-
    make_vertex([], Vertex),
    vertex_value(Vertex, Value),
    ground(Value).

find_vertex_helper(Value, _, Vertex) :- vertex_value(Vertex, Value).
find_vertex_helper(V1, Cache, V2) :-
    vertex_arcs(V2, Arcs),
    instantiated(vertex_instantiated, Arcs, InstArcs),
    subtract(InstArcs, Cache, FilteredArcs),
    union(Cache, InstArcs, NewCache),
    findnsols(1, V, (member(V, FilteredArcs),
                     find_vertex_helper(V1, NewCache, V)),
              [V2]).

find_vertex(_, [], _) :- !, fail.
find_vertex(Value, [V | Graph], Vertex) :-
    vertex_value(V, Value), Vertex = V
    ;
    vertex_arcs(V, Arcs),
    instantiated(vertex_instantiated, Arcs, InstArcs),
    include(find_vertex_helper(Value, []), InstArcs, [Vertex])
    ;
    find_vertex(Value, Graph, Vertex).

find_or_create_vertex(Value, Vertex, Graph, Graph) :-
    find_vertex(Value, Graph, Vertex), !.
find_or_create_vertex(Value, Vertex, OldGraph, [Vertex | OldGraph]) :-
    make_vertex([value(Value)], Vertex).

add_arc(From, To, OldGraph, NewGraph) :-
    find_or_create_vertex(From, VertexFrom, OldGraph, Graph1),
    find_or_create_vertex(To, VertexTo, Graph1, NewGraph),
    vertex_arcs(VertexFrom, Arcs),
    lookup(VertexTo, Arcs).

make_graph_helper([], Graph, Graph).
make_graph_helper([From-To | Vs], GraphIn, GraphOut) :-
    add_arc(From, To, GraphIn, NewGraph),
    make_graph_helper(Vs, NewGraph, GraphOut).

make_graph(Vs, Graph) :- make_graph_helper(Vs, [], Graph).

make_graph([x1-x2, x1-x3, x2-x1, x2-x3, x3-x5, x3-x6, x3-x4,
            x4-x7, x5-x2, x5-x6, x6-x3, x6-x7], G).
/*    G = [vertex(x7, [_G3910|_G3911]),
           vertex(x4, [vertex(x7, [_G3910|_G3911])|_G3891]),
           _S1, _S2,
           vertex(x3, [_S2, _S1, vertex(..., ...)|...]),
           vertex(x2, [_S3, vertex(..., ...)|...]), _S3],
           % where
          _S1 = vertex(x6, [...]),
          _S2 = vertex(x5, [...]),
          _S3 = vertex(x1, [...]) */


Machine Learning: how to correctly calculate gradient descent for simple linear problem So, I was trying to learn machine learning, and, after watching a couple of Andrew Ng's lectures decided to try and write a simple piece of code to determine what someone's salary would be based on the number of years they worked at a company by this simple linear function:

salary = w1 * numberOfYears + w0

I then used the least square method to calculate the error between the predicted results and the actual results and tried to minimize the error of the gradient of that function:

Error = (1/2) [ sum of (predicted - actual)^2 for all samples (x, y) ]

The predicted value is the one calculated by the linear equation above, and actual = y.  w1 and w0 are weights to the function that are set to some initial values (0 and 0 for example) and are changed to decrease the error throughout the process of gradient descent.

Steps to the algorithm:

1)  Choose some (random) initial values for the model parameters (w).
2)  Calculate the gradient G of the error function with respect to each model parameter.
3)  Change the model parameters so that we move a short distance in the direction of the greatest rate of decrease of the error, i.e., in the direction of -G.
4)  Repeat steps 2 and 3 until G gets close to zero.

In my implementation I have this code:

for(int i = 0; i < numSamples; i++) {
    double error = prediction(data.X[i]) - data.Y[i];
    while(nearsZero(error)) {
        for(int j = 0; j < w.length; j++) {
            w[j] -=  0.1 * error * data.X[i][j];
        }
        error = data.Y[i] - prediction(data.X[i]);
    }
}

If I run this with only one sample (meaning ignore the outermost loop), then the weights continuously subtract a value that is continuously nearing infinity (or -infinity).  If I change the w[j] -= ... to a w[j] += ... then the function works for the first value and sets initial w that will solve it for one sample (but that isn't what I was supposed to do as far as I can tell).  Also, when I add multiple samples the numbers just do the same thing on the second sample that they were doing on the first sample when I had -=.

I feel like gradient descent doesn't make sense here because it was demoed on graphs like z=y^2+x^2, which looks like a big bowl with one central min that it will find eventually.

On the graph in my problem the graph looks like a parabola that extends to infinity in both directions and has infinite min values along a line.

I'm not sure what it is that I am doing wrong, but I would assume that it's something to do with my understanding of the problem.  If anyone knows how to get this working I would appreciate it.

EDIT: Updated data.X[i] in the while loop to data.X[i][j].  Each data point i should have some value Y[i] and an array of X values at X[i].

First off, your gradient is error*x1 with respect to w1, but not to w0. The gradient for w0 is just error.

Second, you're computing error with the wrong sign. It should be predicted - actual, not the other way around. What you're doing is essentially adding the gradient at every step.


Is this an instance of a well-known problem? Context

I am developing an application and came across a problem that seemed difficult to solve. Before attempting to reinvent the wheel (and trying to solve an NP complete problem on my own), I would like to get some feedback. Below you will find an abstract version of the problem.

The Problem

Input:

A bag of colored balls. A ball may have many colors (e.g. red, blue and yellow) or only one (e.g. green). Each ball has also a score. Since we are talking about a bag, elements may be repeated.
A set of colored boxes, one per color. Each box is labeled with a natural number.

Problem: each colored box must be filled with the exact amount of balls specified by its label.

Constraints:

The color of the balls in a box must match the color of the box (e.g. a green ball goes in a green box).
A ball of many colors can be assigned to a box of any of those colors (e.g. a ball that is both red and green can either go in a red box or in a green one).

The solution to the problem can be represented by the following information: for each box, a list of the balls it contains (a ball is represented as a list of colors and a score).

Output of the algorithm: the solution with the highest score. The score of a solution is the sum of the scores of all balls in the boxes (of course, there may be many solutions, but in that case we just pick one of them).

Current research

Somehow this problem makes me think of Sudoku, which is an instance of the exact cover problem. However, I haven't been able to come up with a way to model this problem in terms of exact cover and am afraid I may be missing a more straightforward approach.

As suggested in the answers, another possibility would be to model this using max-flow. However, this approach is unable to generate all possible solutions such that each box is filled to its capacity. Furthermore, the max flow value is known to be the sum of the capacities of the boxes (it is assumed the number of balls is large enough for this to happen).

Questions

Is this an instance of the exact cover problem? If yes, how would you model it in terms of exact cover? If no, is it an instance of any other well-known problem?

Isn't this a case of max-flow?

Model your problem as a bipartite graph, from ball to boxes, with an edge from each ball to the boxes with matching colour. Each of these edges has capacity 1. Now add source and target vertices. From source to each ball with capacity 1. From each box to target, capacity is the capacity of the box.

Now you want to enumerate all solutions to this max-flow problem (i.e., output all flows whose value achieves the maximum possible). But that might be a lot of solutions!

(edit) A recent update has added scores to the balls, and the target is to maximize the scores of the balls that are put into the boxes. I would suggest maximal bipartite matching where you have as many copies of nodes for each box as the capacity of that box. As there will be balls that do not fit into the boxes I would suggest adding boxes for overflow balls (to obtain complete matching, when necessary). Wikipedia suggests the Hungarian algorithm.


Rigorous error bounds for eigenvalue solvers I computed the first four eigenvalues of a quite large ($2^{24}\times 2^{24}$) but very sparse matrix. I used pythons in-build function sparse.linalg.eigsh to compute them.
I need a validation that the results are correct up to an error of at most $10^{-3}$.

Very specifically I want to ask if there is a rigorous error-analysis involving rounding errors up to machine precision in each step.

More generally: Are there other practical algorithms for eigenvalues with such a rigorous error analysis.

It might suffice to ask the solver to give you both the eigenvalue $\lambda$ and the corresponding eigenvector $v$.  Then you can verify for yourself how much error there is.  Note that if $\lambda$ is the eigenvalue corresponding to eigenvector $v$, for matrix $M$, then we have $Mv=\lambda v$.  So if you know $M$ and $v$ exactly, and you have a claim that $\hat{\lambda}$ is within $\epsilon$ of the true eigenvalue $\lambda$, it suffices to check that

$$(\hat{\lambda}-\epsilon)v \le Mv \le (\hat{\lambda}+\epsilon)v$$

where $\le$ is to be interpreted separately for each index, i.e., you should check that $(\hat{\lambda}-\epsilon)v_i \le (Mv)_i \le (\hat{\lambda}+\epsilon)v_i$ holds for each index.

If there is some error in the eigenvector $\hat{v}$ returned by the solver, then there is the possibility that the above check might fail, even if $\hat{\lambda}$ is indeed a true eigenvalue of the matrix.  I don't know whether there's a nice way to adapt the above calculation to address this issue.  If the operator norm $\|M\|_1$ is small, then it might work to check that

$$(\hat{\lambda}-\epsilon)\hat{v}_i -c \le M\hat{v} \le (\hat{\lambda}+\epsilon)\hat{v} + c$$

where $c = \|M - \hat{\lambda} \text{Id}\|_1 \times c'$ and $c'$ is an upper bound on the amount of error in $v$ (measured in $L_1$ distance) that you're willing to tolerate.  I'm not sure if this is exactly right; there might be issues in this last criterion, so check it yourself before believing in it.


Show that language of distinct binary strings is irregular Let $Σ =\{\textbf{[},\textbf{]},\textbf{,},\textbf{0},\textbf{1}\}$, and let $L⊂Σ^*$ be the language containing list representations of finite sets of binary strings: i.e., every string $x∈L$ is of the form $x= \textbf{[}x_0\textbf{,} x_1\textbf{,} \ldots\textbf{,} x_n\textbf{]}$, where:

for all $0\le i\le n$, $x_i$ is a string in $\{\textbf{0},\textbf{1}\}^*$, and
none of the $x_i$ repeat: if $i$ is not equal to $j$, then $x_i$ is not equal to $x_j$.

Show that $L$ is not regular.

$\
\\$

$\textbf{EDIT: Below is my attempt: }$

Suppose $L$ is regular.

Suppose the pumping length is n.

Consider the string $x$ = $[0^n, 0^{n-1}, ... , 0]$.

By the Pumping Lemma, $x=uvw$, where

$u$ = $[$
$v$ = $0^n$, $0^{n-1}$, $0$
$w$ = $]$

Then, $|v|>0$ and $|uv| \leq n$

So, $x \in L$ and $|x| \geq n$.

$\
$

Choose $k=2$.

Then, $uv^2w$ = $[0^n, 0^{n-1}, ... , 0  0^n, 0^{n-1}, ... , 0]$

Since each of the strings in x are repeated, this is a contradiction to the Pumping Lemma. Therefore, $L$ is not regular.

Suppose that the pumping length is $n$. Consider the string
$$
w = [0^n,0^{n-1},\ldots,0].
$$
You take it from here.


The law of excluded middle and decidability I will divide my question in two parts. The first part I am sure that there is a objective answer, but I am not sure about the second part.

First part:
Is it all (decisions) problems trivial to prove decidable after assuming the Law of Excluded Middle (LEM)? e.g. There is no problem hard to prove decidable after assuming LEM.

Second part:
Does make any sense to agree with a non-constructive proof that a problem is decidable?

Edit:

I will give an example of what I meant in the first part.

Consider the problem of deciding the eveness of a number.
If I assume LEM, this problem can be easily proved decidable. There was no need to do the "hard" proof of building the decider.

Here is the demonstration in Coq of that:

Inductive even : nat -> Prop :=
| ev_0 : even 0
| ev_SS : forall n, even n -> even (S (S n)).

Axiom LEM : forall P : Prop, P \/ ~ P.

Lemma even_dec : forall (n : nat), even n \/ ~ even n.
  intros.
  apply LEM.
Qed.

The first part of my question was basically asking if this is always the case.

You are conflating computationally decidable with logically decidable.

A (closed) formula, $\varphi$, is logically decidable iff $\vdash\varphi$ or $\vdash\neg\varphi$, i.e. if $\varphi$ is derivable or $\neg\varphi$ is derivable (with respect to some given logical system). This is the sense we mean when we say something like the Continuum Hypothesis is undecidable.

A unary predicate on naturals, $P$, is computationally decidable iff there is a Turing machine $M$ which terminates on all inputs with output either $1$ or $0$, and $P(n)$ holds if and only if $M$ terminates with output $1$ on input $n$. This is the sense we mean when we say something like the Halting Problem is undecidable.

(There are other ways we use the term "decidable" such as when we say a(n entire) logic or theory is decidable which, more or less, means something like $\vdash\varphi_n$ is computationally decidable where $\varphi_n$ is a formula encoded by $n$ via some suitable surjective encoding.)

Assuming the Law of the Excluded Middle (LEM) doesn't automatically make every unary predicate on the naturals computationally decidable. Indeed, usually computational decidability is formulated within a classical logic where LEM holds.

Intuitionistic logic connects logical decidability to LEM because it satisfies the disjunction property which states $\vdash\varphi\lor\psi$ if and only if $\vdash\varphi$ or $\vdash\psi$. This means $\varphi$ being logically decidable is equivalent to $\vdash\varphi\lor\neg\varphi$.

Now, there's a model of intuitionistic first-order logic such that $\forall n:\mathbb N.P(n)\lor\neg P(n)$ is modeled by a computable function taking a natural and producing a witness of (the interpretation of) either $P(n)$ or $\neg P(n)$. This means (the interpretation of) $\forall n:\mathbb N.P(n)\lor\neg P(n)$ is true in this model if and only if $P$ is computationally decidable. LEM, in this context, would imply the statement that all decision problems are computationally decidable. LEM is, of course, false in this model. Therefore, if you assume LEM, this interpretation ceases to be a model.

The fact that certain formulas are derivable in intuitionistic first-order logic implies that corresponding predicates are computationally decidable. This implication itself, though, is demonstrated in the meta-logic where the definition of "computationally decidable" resides, and this is usually a classical logic.

For an informal (meta-)logic in which you define "computationally decidable", it's up to you whether you want to accept non-constructive proofs or not. However, there is a big difference between proving a formula in constructive logic which can be interpreted as a witness to the computational decidability of a predicate, and proving a formula which states in the constructive logic that a predicate is computationally decidable which would involve constructive definitions of Turing machine and so forth. As an analogy, the circle as a (higher inductive) type in Homotopy Type Theory is very different from the construction of cirles, e.g. $\mathbb R/\mathbb Z$ within Homotopy Type Theory. As a more contrived example, let's say I interpret the theory of abelian groups into $3\mathbb Z$, i.e. $1$ is interpreted as $3$. Then it is still the case that the "internal" notion of $3$, i.e. $1+1+1$, is different from $1$.


Design a Turing Machine Checking if Apples and Bananas are Even I am having trouble with a past exam paper. I have to design a Turing Machine to do the following, but I don't really know where to start with this question. Any help would be very much appreciated.

Design a Turing Machine TM checking if the numbers of sold apples and bananas are even. Formally, given a string w over the alphabet {a,b}, TM should terminate with the following result string.

ab if the number of apples and bananas are even
a if the number of apples is even but bananas are odd
b if the number of apples is odd and bananas are even
ϵ if the number of apples and bananas are both odd

Thanks

I'm not going to give you a direct solution, but let's think about this problem together, shall we? We will focus on 4 states. Why four? Well, you have two variables, each with two possible states, so $2^2 = 4$. So, for right now let's call our states $1$, $2$, $3$ and $4$:

$1$ is the state denoting an even number of apples and bananas. This is our start state.
$2$ is the state denoting an odd number of apples and an even number of bananas.
$3$ is the state denoting an even number of apples and an odd number of bananas.
$4$ is the state denoting an odd number of apples and an odd number of bananas.

Now, let's see how we move between states. For the moment, let's ignore the possibility of $\varepsilon$ for the input.

From state $1$ ($a$=even, $b$=even):

If we get an $a$, go to state $2$. Eat the apple and output nothing.
If we get a $b$, go to state $3$. Eat the banana and output nothing.

From state $2$ ($a$=odd, $b$=even):

If we get an $a$, we go to state $1$. Eat the apple and output nothing.
If we get a $b$, we go to state $4$. Eat the banana and output nothing.

From state $3$ ($a$=even, $b$=odd):

If we get an $a$, we go to state $4$. Eat the apple and output nothing.
If we get a $b$, we go to state $1$. Eat the banana and output nothing.

From state $4$ ($a$=odd, $b$=odd):

If we get an $a$, we go to state $3$. Eat the apple and output nothing.
If we get a $b$, we go to state $2$. Eat the banana and output nothing.

At this point we are pretty full and sick of apples and bananas. So let's consider what happens when we run out of food. It should be clear that we are going to be in one of the four states above. So let's augment each of them with an additional rule each:

The rule is simple: when the input for any one of those states is $\varepsilon$, output the correct sequence of characters for that state and then go to a $halt$ state.

I hope this helps!


result after applying on delete cascade In this table B is foreign key referring to the primary key A with on delete cascade option.What will be the result after deleting (4,3) and how
A:1 4 2 9 3 5
B:3 3 4 2 9 4

The result will be an empty table.

The steps are :

delete (4,3)
delete rows with B = 4        --> (2,4), (5,4)
delete rows with B = 2, B = 5 --> (9,2)
delete rows with B = 9        --> (3,9)
delete rows with B = 3        --> (1,3)


Automata with no transition for some character Given an automaton and an alphabet $\{a, b\} $,  and the language accepted by the automaton is $ab^*$.

Such an automata can be found here:

My question is: this automaton cannot process the word $ba$ for example. In general,  do automata have to be able to process any word?

In a deterministic automaton, every state must have exactly one transition for each symbol in the alphabet. In a nondeterministic automaton, this requirement is dropped and there could be multiple transitions or no transition for some symbol. If there is no transition for the next character in the string, the automaton rejects its input. This is what happens with the automaton on the left: it rejects the string $ba$ (and every other string beginning with $b$) because it has nowhere to go when it reads that first $b$.


Hash function to hash 6-digit positive integers Let UID denote a unique identifier. UID's are represented as 6-digit positive integers.

I want to insert a collection of UID's in a hash table with $M$ buckets, where $M$ is a prime number (for example, 524309).

If I am not mistaken, since $M$ is prime, dividing an UID with $M$ generates a unique remainder, as there is no common factor, except 1.

Example 1: UID = 222222 and $M$ = 524309.

Example 2: UID = 524309 and $M$ = 524309. In this example, the UID is hashed to bucket number zero in the hash table. The hash function is h(UID) = UID % M.

The question is: can hash function h avoid collisions for any 6-digit UID?

If yes, what is the mathematical approach to prove it?

A hash table usually uses two different things: One, a hash function that maps an item to a hash code (with the requirement that equal items are mapped to equal hash codes), and two, a function that maps hash codes to locations in the hash table where the item would be stored.

Hashing every UID to a different 32 bit hash code is trivial - just hash every UID to itself. No collisions. The mapping function of the hash table should be implemented in a way that common hash functions don't lead to many collisions. Many hash functions either produce results that look like random, or like in this case might produce many consecutive values, so using a prime number as the hash table size and (hash code modulo hash table size) as the first location for the location in the table works quite well.

Since you have one million items, and 524309 entries, it's impossible to guarantee no collisions. In practice, that's not a problem. What counts is the time for calculating the hash code, plus the average time for finding and checking one or more locations in your hash table. As long as the average number of collisions is small, you are fine. And there is a simple way that usually keeps the number of collisions small: Use a generous size for the hash table.


Tool for generating all the consequences of the logical theory (general logic programming framework)? I am reading article https://arxiv.org/pdf/cs/0511055v1.pdf (about defeasible deontic logic) and it mentions on page 10 the operator T that constructs extension (set of immediate consequences) from the theory D (set of statements). Such extensions form s.c. Kleene sequence and the fixed point exists for the operator T - this fixed point is the complete set of consequences of the set D of statements.

Such construction is known for many logics and I guess that it is the basis of the logic programming using forward chaining approach. This approach is known in business software as well and is called business rules (e.g. JBoss Rules Drolls of IBM ILOG). Such construction has very wide practical applications, e.g. if norms are encoded as logical statements then the set of consequences consist of all the obligations and permissions. More practical applications can be found as well - e.g. application of complex discounting rules in retail trade.

My theory question is:

Do I understand correctly that generation of set of consequences is the essence of logic programming and such logic programming can be devised for almost any logic?

My systems questions are:

Are there general framework (system) which receives 1) syntax of logic; 2) operator T and which generates program that can find set of consequences for any set D? I.e. should I construct logical programming tool for my logic from scratch (only parser can be generated automatically) of can I use some framework?
How such logic programming framework is connected with proof assistant and theorem prover frameworks (like Isabells of Coq)? As far as I understand then there is no connection - theorem provers use backward reasoning approach and logic programming uses forward reasoning approach? However - maybe any connections exists and maybe proof assistant/theorem prover frameworks can still be used for logic programming?

You understand incorrectly. That is not how logic programming works.

The number of consequences typically grows exponentially, or is even infinite. For instance, some consequences of $\forall x \in \mathbb{N} \,.\, \phi(x)$ are $\phi(0)$, $\phi(1)$, $\phi(2)$, $\phi(3)$, $\phi(3 + 2)$, $\phi(x \cdot 2)$, and so on. Generating all consequences is infeasable and useless. It's a bit like trying to write good literature by generating all grammatically correct sentences.

The gist of logic programming is proof search. A logic program follows a particular strategy to look for the proof of a given query. So in this sense, it does things backwards.


Why does Python allow stand-alone expressions? In Python, this is a valid program
def PrintWorld():
    print('World')

print('Hello')
0
'beautiful'
True
None
0 < 0
3, 3
lambda c:3
PrintWorld()

All it does is print 'Hello World' on two lines. The expressions are 0, 'beautiful', True, None, 0 < 0, 3, 3, and lambda c:3 are ignored and I'm wondering why.
I realize that this behavior allows Python to treat the function call PrintWorld() like any expression: It is an expression with value None in the course of whose evaluation the function is called. In a sense, this means that both 'beautiful', PrintWorld(), and a hypothetical expression with side effects like PrintWorld() is None could be treated the same on some level.
I also realize that this is related to interactive mode: When you run the Python interactively, giving only a stand-alone expression will result in its value being printed.
Still, why should non-interactive mode accept these expressions (except function calls)? In my eyes they open up the possibility for pointless code without offering anything in return.
And, as a follow-up: If you do allow these stand-alone expressions, why have comments or a pass statement in the language when you could just use a stand-alone expression instead?  Sure, "explicit is better than implicit", but it's also valuable to keep the language small.
As research I googled and searched stack overflow and CS stack exchange. I also looked into the Python language definition.

The python creators decided that any expression is valid as a statement. While not all expressions are useful as statements, it would make the language more complex to have to remember which expressions may be statements and which can not.
A second reason is that many expressions that may seem "safe" can still have side effects, making it useful to evaluate them without using the return value.
Operators
Operators are the most obvious examples of expressions that you can easily add side-effects to. In your example 0 < 0 is equivalent to 0.__le__(0). You can overwrite the __le__ method or any operator special method to do whatever you want, including writing to a file or incrementing a counter.
You can also evaluate operator expressions just to make sure the types are compatible. For example, if you are going to do a very long computation on variables a and b that ends by dividing some value based on a by b you might evaluate a/b at the start of your function as a quick and dirty way to make sure the types can be divided and that b is not zero before spending a lot of time calculating.
Strings
Strings don't typically have any side effects, but string expressions are frequently used in python code as a type of comment. Specifically, docstrings are triple-quoted strings right after the heading of a class or function, and will be assigned to __doc__.
Variables
Evaluating variables has one important function: It will crash if the variable doesn't exit. For example, suppose I have a module server.py that must be configured server.host = 'localhost' before starting. I could write this:
try:
    host
except NameError:
    raise ConfigurationException("must set host")

Tuples
The tuple expression a, b where a and b are expressions will evaluate any side effects from a  b.
Others
Ok, there is little use for a loose None. However, only disallowing None, True, False, Ellipsis, NotImplemented, and ... would be a unnecessary special case that would make the language harder to learn for little benefit.


Password authentication over an insecure connection I was thinking a way to send password to server secure way without using secure connection,I found one solution.I want to find flaw in this.(Note: I am begginer,dont judge me, I know little about cryptography and little about networks)

So server contains hashed version of my password.
When i want to send password I send server request to generate me random key(big enough it is less likely to be same ).
Then I hash password and add that hash to key and hash it again.I send that final hash to server.
Server use key and hash the hashed password from database the same way and compare my hash with it.If it is the same,password is correct.

Ex. (Simplified)
I want to send password "test123" to server.
I request random key and server sends me key "999".
I hash "test123" and get lets say "abc" ,and hash "abc999" and get "efg" and
send that to server.
Server recieves my "efg" , then gets "abc" hashed password from database, adds key "999" and gets "efg" ,so "efg"=="efg"  ,password correct.

The someone listening the connection can't use the same hash because it will get different key.

If you don't use a secure connection, it is vulnerable to man-in-the-middle attacks, so not secure.

If you do use a secure connection, then it is no better than sending the password directly.


Viterbi Algorithm: initial state with ONE probability The Viterbi Algorithm can be used to calculate the most likely path, based on observations in a Hidden Markov Model.

Using the same notations as Wikipedia, "each element T1[i, j] of T1 stores the probability of the most likely path so far X = (x[1] , x[2] , ... , x[j])  with x[j] = s[i] that generates Y = (y[1] , y[2] , ... , y[j]).

Now suppose, that the initial distribution $\pi$ is such that for one state the probability is 1 (let's call it state K), and for all other states it is 0. Also, let's say that in the emission matrix B all elements are strongly between 0 and 1 (i.e. 0 < B[i, j] < 1 for all i and j.

In this way 0 < T[K,1] < 1 and for all other states T[i,1] = 1.

Problem:
For me, the part T[K,1] < 1 feels intuitively wrong. How can it be, that the first state is K, with probability 1, still the most likely path contains it with probability less than 1?

I understand that the reason must be something like: "There are more different paths. One where the first state is K, and the first observation is y1. One, where the first state is K, and the observation is y2. Etc.".

However, it is also true, that "no matter what the observation is, the first state is K with probability 1".

Question: What is the explanation for this (seeming) contradiction? (The best would be if it is "intuitive".)

Wikipedia is wrong.  That's not what $T_1$ stores.  Rather, $T_1$ stores the likelihood of a path... namely, the likelihood of the path that has the highest likelihood.  What's the likelihood of a path $\hat{X}$?  It is the probability of generating the output sequence $Y$ given that you followed the path $\hat{X}$, i.e., the probability $P(Y | \hat{X})$.  Note that this is not the same as $P(\hat{X} | Y)$.

The probability $P(Y | \hat{X})$ might be less than 1, even if we're certain that $\hat{X}$ was the path that was followed.  In particular, you can have $P(Y | \hat{X}) < 1$ even if $P(\hat{X}) = 1$.  This can happen, for example, if there are multiple possible output sequences that could arise when following the path $\hat{X}$.

As usual, Wikipedia is not a primary source.  Don't use Wikipedia as your only source for learning new material.  It is helpful as a summary, but when you find something in Wikipedia that is confusing or that doesn't make sense, go to a primary source -- e.g., a highly reputed textbook.  Wikipedia does have errors, poor writing, gaps in its explanation, and so on, so it is not a substitute for a high-quality primary source.


Is there any connection between imperative programming and the Von Neumann architecture? I have ran into a wall with this question in the exercise my teacher gave me, is there any actual connetion between the Von Neumann architecture and imperative programming ?

I have tried googling and finding questions similar to this, but I couldn't find anything, and the one question that I have found actually said that there shouldn't be any connection between the Von Neumann architecture and programming paradigms.

Any help would be appreciated, I'm new to StackExchange, so if I'm breaking any rules please do tell me :)

von Neumann architecture is memory for data and instructions and a CPU that fetches and executes instructions one after the other. That is intrinsecally imperative. Compare with functional programming (define functions that call among themselves) or logic programming (search for a solution  to a set of logic statements). Other paradigms like OOP are more or less orthogonal to the above.


A problem to maximize the number of edges in a cycle while minimizing the total weight I encountered the problem below and the only solution I came up with is branch and bound like that is used in TSP and I don’t think the bound I used is good enough. Are there any better idea on this?

Consider a graph $G$ that consists of an undirected bipartite graph and another vertex $O$ that is connected to all the other vertices. Assume the weight of the edges are positive and the weights obey the triangle inequality. Find a cycle in $G$ that involves $O$ s.t. the total weight is $\leq$ some given value $t$ and maximize the total number of vertices it passes through.

This is NP-complete, since an instance $(V,E)$ of the NP-complete problem Hamiltonian Path can be reduced to it: Turn each vertex in the original HP instance into a pair of vertices $a_i, b_i$ connected by a low-weight edge, with one vertex in each part of the bipartite graph, and add a high-weight edge $a_ib_j$ for each edge $v_iv_j$ in the original graph. Finally add $O$. Solve your instance and delete $O$: the original graph has a HP iff $2|V|−1$ edges remain.

All this is to say there is almost certainly no polynomial-time algorithm to solve your problem (since if there was, Hamiltonian Path, and every other NP-complete problem could also be solved in polynomial time).  Adapting an algorithm for solving TSP sounds reasonable to me.


Can we multiply approximation hardness? Say we have two (NP-)optimization problems $A$, resp. $B$, such that it is NP-hard to approximate within a factor $\alpha$ resp. $\beta$.

Now define problem $C$ whose input consists of pair inputs from $A$ and $B$, and a solution as pair of solutions of $A$ and $B$, but the objective function as the product of objective functions of $A$ and $B$.

Can we conclude that $C$ is NP-hard to approximate within a factor $\alpha\beta$?  If not, can we prove anything stronger than that there is no approximation within $\max\{\alpha, \beta\}$? If yes, does it matter if the hardness depends on, for example, the unique games conjecture?

Intuitively, I would think: unless $P=NP$, for any polytime approximation algorithm for $A$ there is an input such that it gives a solution of cost more than $\alpha OPT$, and likewise for $B$. Any algorithm for $C$ can be used almost directly as an algorithm for either $A$ or $B$, so we can find an input that produces a solution of cost more than $\alpha \beta OPT$ on that algorithm as well. I am not sure if you can reason like this though.

When we say that a minimization problem A is NP-hard to approximate up to a factor $\alpha \geq 1$, we mean that there is a polynomial time reduction $f$ from instances $\varphi$ of SAT to instances $x$ of A annotated by a target value $\theta$ such that:

If $\varphi$ is satisfiable then $A(x) \leq \theta$ (where $A(x)$ is the optimal value of $x$).
If $\varphi$ is not satisfiable then $A(x) > \alpha \theta$.

Using this definition it is not hard to prove the multiplicative property.

You can also consider a more general notion of hardness: if there is a polynomial time $\alpha$-approximation algorithm for A, then P=NP. Even under this notion, a $\alpha$-hardness for A translates to a $\alpha^2$-hardness for "A2". Indeed, given an instance of A, duplicate it and pass it to the $\alpha^2$-approximation algorithm. One of the solutions is an $\alpha$-approximation. If only the objective value is given, then the smaller one is an $\alpha$-approximation.


Optimal root in shortest path tree (SPT) I would like to find the "optimal" shortest path tree (SPT) in some undirected weighted graph. As "optimal" SPT, I mean so its maximal path from root to leaf is minimal from any other potential SPTs.

It is quite easy to find SPT from 1 root via Dijkstra's algorithm. So I can run Dijkstra from all vertices and find the "optimal" SPT and its root.

Is there any faster algorithm?

This problem is equivalent to computing the radius of a graph. The best known algorithms for computing radius essentially compute all pairs shortest paths, so the method that you suggest cannot be improved much. If the number of edges is large, maybe Floyd–Warshall algorithm could be faster.

References:

https://en.wikipedia.org/wiki/Distance_(graph_theory)

https://arxiv.org/abs/1506.01799


How to interpret plot of cost function in gradient descend algorithm? I have a data set to which I want to apply logistic regression. I set my cost function to be

$J(\theta) = -\frac{1}{m} [\sum\limits_{i=1}^{m} y^{(i)} log{(h_\theta \cdot x^{(i)})} + (1-y^{(i)}) log(1-h_\theta(x^{(i)}))$

and I am running gradient descend algorithm.

When I plot the cost function as a function of the number of iterations, I am getting a plot like this

Which I think is a good sign.

However, when I zoom in on the initial portion of the curve, I get this plot

I don't know what to make out of the rising and falling in the cost in the beginning. Is that something that we can expect? If so, why? Shouldn't the gradient descend algorithm decrease the cost after every step? How is it that after some iterations there is an increase in the cost? I know that it is possible for gradient decent not to converge if the learning rate is big enough but the algorithm does seem to converge eventually. So why is it that there are some instances where gradient descend tends to increase the cost?

I don't know what to make out of the rising and falling in the cost in the beginning. Is that something that we can expect? If so, why? Shouldn't the gradient descend algorithm decrease the cost after every step?

Gradient descent only minimizes the cost if the learning rate is low enough. Also, in practice most of the time you don't use gradient descent on the whole dataset, but on a mini-batch. This means you don't get an guarantee that the global cost is falling for a single step.

An analogy which is often used is that of a landscape with hills. The landscape is your cost. Each point in the landscape is a specific configuration of weights. The gradient shows in the direction of steepest descent. That might be a rabbit hole on a hill, but it might also be downwards to the valley. Now, imagine it shows to the rabbit hole. Instead of going down the rabbit hole, you make a bigger step and so you go up the hill. But then you are on a different position. For your next step, you come away from the rabbit hole and get towards a better (local) minimum.

As always when it comes to training, I would like to point out the awesome gifs by Alec Redford: Gifs 1, and Gifs 2


What are Contexts in Lambda Calculus? What is a Context? Is it like a scope in C? Does it have a start and an end? Can contexts contain other contexts?

I see Contexts being used in lambda calculi type system rules, but I don't understand concretely what they are and why they are necessary. If they are too abstract, then is there some visual or metaphorical description?

Update: I am referring to "contexts" as what is to the left of ⊢ in typing calculi.

Typing contexts are the way to remember previously declared variables when type-checking a program/term. The rule for term abstraction usually is something like
$$\dfrac{\Gamma,x:A\vdash e : B}{\Gamma\vdash \lambda x.e : A\to B}$$
In the conclusion, $x$ is not in $\Gamma$ yet. At this point, $x$ is declared to be the variable of the function $\lambda x.e$ and this variable appears in $e$. So, $x$ is a free variable in $e$. The typing rule above expresses that $\lambda x.e$ is of type $A\to B$ under context $\Gamma$ iff $e$ is of type $B$ under context $\Gamma,x:A$. So in the premise of the rule, we are type-checking the body of $\lambda x.e$ (which is $e$), but we need to remember that $x$ (which appears free in $e$) is a variable of type $A$.


Is there a programming language that is not a formal language Are out there, any programming languages that are not defined algorithmically so that we can call them "constructed languages" but not "formal languages"? Are there any discussions or papers on that topic? It seems pretty hard to develop a compiler for this kind of languages.

No, at least not a reasonable programming language by what we commonly understand under that term.

As soon as you have a compiler (or an interpreter), you have an algorithm that decides whether a given string is a valid program. This compiler then defines the language. (Not a good way to define a programming language, but a workable one.)


LaTex Text Justification badness penalty I had been going through dynamic programming concepts and happened to read about text justification problem in which the spaces to the right of the line end are penalized with cubic times the number of spaces. The algorithm also works with quadratic times number of spaces as penalty. I have couple of questions 1) Any idea why this works with both cubic & quadratic? 2) Why it should be cubic or quadratic why not just linear?

The optimization function is designed in a way to find a solution that:

uses a small number of lines
is balanced (the number of extra spaces at the end of each line should be about the same length)

Lets look first at the linear optimization function, i.e. the sum of all extra spaces.

It is very clear, that the optimal solution under that function is one that uses the minimum number of lines.
However it will not fulfill the second goal.
The number of extra spaces is equal in each solution that uses the same number of lines.

For instance if you want to split the string a.bb.ccc at line-width 6.
The unbalanced solution

a.....
bb.ccc

has the same penalty 5 (number of extra spaces) as the balanced solution

a.bb..
ccc...

. So if you only optimize with a linear function, then you might end up with an unbalanced solution.

Now lets look at the the sum of squares.

The intuition is, that having lines with a lot of extra spaces will get penalized a lot more than lines with less extra spaces.

Using the same example. The unbalanced solution

a.....
bb.ccc

will get a bigger penalty $5^2 + 0^2 = 25$ than

a.bb..
ccc...

which has only a penalty of $2^2 + 3^2 = 13$.

You can actually partially prove that this will give us a balanced solution.

If you fixate the number of lines, than also the number of necessary extra spaces is fixed. Let's assume than we need $n$ lines with $m$ extra spaces. I'll denote $a_i$ for the number of extra spaces in line $i$.

We want to optimize $$\sum_{i = 1}^n a_i^2$$
We know (using the QM-AM inequality), that

$$\sum_{i = 1}^n a_i^2 \ge \frac{(\sum_{i=1}^n a_i)^2}{n} = \frac{m^2}{n} = \text{const}$$

and that we reach equality for $a_i = \frac{m}{n}$ for all $i$.

So the minimum of the optimization function is reached, when every lines has exactly the same number of extra spaces.

Notice, that usually this is not possible (because of the different word lengths in the string).

But the result supports the argument, that this optimization function ends up with a solution that we human would call "balanced".

The cubic function, and many other ones, will work in exactly the same way. Unbalanced solutions will end up with a higher penalty than balanced solutions.

Btw, $\LaTeX$ uses the sum of squares as penalty. At least Wikipedia claims so.


Why is tabulated hashing 3-wise independent but not 4-wise independent? Tabulated hashing uses tables of random numbers to compute hash values.
Suppose $|\mathcal{U}| = 2^w \times 2^w$ and $m = 2^l$, so that the items being hashed are pairs $(x,y)$ where $x$ and $y$ are $w$-bit strings (or $2w$-bit strings broken in half), and hash values are
$l$-bit strings.
Let $A[0 \cdots 2^w-1]$ and $B[0 \cdots 2^w-1]$ be arrays of $l$-bit strings. $A$ and $B$ can be though of as $2^w \times l$ dimensional array of bits.
Define the hash function $h_{A, B} : \mathcal{U} \to [m]$ by setting $h_{A, B}(x, y) = A[x] \oplus B[y]$, where $\oplus$ denotes bit-wise exclusive-or.
Let $\mathcal{H}'$ denote the set of all possible functions $h_{A, B}$.
Can someone explain  why is  $\mathcal{H}'$ 3-wise independent and not 4-wise independent?


Is it possible to do face recognition with just the eyes? Assuming the input photo is focused on a person's face, if the person is wearing a surgical mask, most face recognition software fail to identify the subject's face.
Most facial landmark models are trained to identify at least the eyes and the tip of the nose (for example, dlib's 5 point landmark).
Is it possible to construct a model that is trained to identify a face based on only the eyes?

Recognising the right face is not the problem. Reliably rejecting the wrong face is.


Proving the set of finite languages is countable without using the union of countable sets The list of finite languages over a finite alphabet is countable.

I could prove it by saying that the list of languages of size 1 is countable, the language of size 2 is countable, and so on. Then I can prove that the infinite union of countable set is countable.

However, I am sure that there is a simpler proof. Can someone help?

In my example $|\Sigma=\{0,1\}|$

Let your finite alphabet be $\Sigma = \{a_1, \dots, a_\ell\}$ and let $\#$ be some character not in $\Sigma$. Let $L=\{w_1, \dots, w_n\}$ be a finite language over $\Sigma$. You can consider the string $\#w_1\#w_2\#\dots\#w_n$ to be a number in base $|\Sigma|+1$ by associating the symbols $a_1, \dots, a_\ell, \#$ with the base-$(|\Sigma|+1)$ digits $0, \dots, \ell-1, \ell$, respectively (starting the string with $\#$ ensures that the leading digit isn't zero). This gives a map from the set of finite languages over $\Sigma$ to a subset of the integers, so that set of languages is countable.


Applying a 1x1 convolution on an existing layer I am looking at the following github. In this, layer3 has a shape of (1, 20, 72, 256) and I interpret this is as a single layer having 20 input nodes and mapping to 72 output nodes and there are $256$ filters, so the depth is $256$. Then, after applying a 1x1 convolution to this, the new shape becomes (1, 20, 72, 2). I don't quite understand how this comes about.

Is it because there are only 2 classes in the model, so it only needs a depth of two at all points? I keep stumbling over the code and can't get anywhere.

A $1 \times 1$ convolution is a modern technique for dimensionality reduction, originally proposed in the Inception paper by Google team.

Suppose the layer outputs a $(N,H,W,F)$ tensor, where $F$ is the number of feature maps. Then the number of floating-point operations that the subsequent convolutional layer is going to compute is $O(N \cdot H \cdot W
 \cdot F)$, most importantly it's proportional to $F$. Likewise the number of parameters is also proportional to $F$ and the filter size.

The problem is that deep convolutional networks tend to increase the number filters exponentially, so $F$ can be really large, which makes training deep networks pretty expensive.

The idea is to reduce the size of the tensor via clever application of the convolution to $(N,H,W,F')$, where $F'$ is much smaller than $F$. If the network learns to compress the information of $F$ feature maps into $F'$ feature maps, the whole network will become much lighter both in terms of memory and computational complexity, yet potentially deeper. As it turns out, this trick works magically, so that it's used all over the place before expensive convolutional layers:

  One big problem with the above modules, at least in this naive form, is that even a modest number of 5x5 convolutions can be prohibitively expensive on top of a convolutional layer with a large number of filters.

  This leads to the second idea of the proposed architecture: judiciously applying dimension reductions and projections wherever the computational requirements would increase too much otherwise. This is based on the success of embeddings: even low dimensional embeddings might contain a lot of information about a relatively large image patch...1x1 convolutions are used to compute reductions before the expensive 3x3 and 5x5 convolutions. Besides being used as reductions, they also include the use of rectified linear activation which makes them dual-purpose.

The trick itself is pretty simple: apply $F'$ convolutions with $1 \times 1$ kernel size. This doesn't change spatial dimensions of the image, but only reduces the depth.

This is exactly what happened in your case: the depth was reduced from 256 to 2, which is a 128x boost for the subsequent layer.


Quicksort $T(n)_{best}=\Omega(n\log n) $ proof About the proof that quicksort has $T(n)_{best}=\Omega(n\log n)$.

I can't find this specific aspect anywhere online which is strange. I'm going through a proof for this in a book and I don't understand something, it says that about analyzing the "cost" of a level in the recursion tree that:

  Since the recurrence relation for quicksort is: $T_{best}=
 T(i-1)+T(n-i) + n$, then the cost of the root is $n$, and the cost of
  the level below it is $n-1$, in general: if a level has $x$ vertices,
  then the cost of the next level is smaller by $x$.

How is that possible? It's easy to see that each complete level has a total cost of $n$.

Also about the first level, if we plug $i=1$ to the equation, we indeed see that one recursive call (say left) leaves a "cost" of $n-1$ but the second call (say right) has a cost of $1$ so the total for the first level is $n$ and not $n-1$..

  The proof then goes on to say that level $i-1$ has at most $2^{i-1}$
  vertices, therefore the cost of level $i$ is at least
  $n-(1+2+...2^{i-1}) > n- 2^{i}$, therefore the cost of each of the
  $\log n $ levels is $\Omega (n)$.

Does anyone understand the part that I'm asking about?

Alternatively, is there a proper rigorous proof for this somewhere online?

You mentioned the quicksort recursion:
$$
T_{best}(n) = \min_i [T_{best}(i-1) + T_{best}(n-i) + n].
$$
Note how in this recursion $(i-1) + (n-i) = n-1$. This is because the two subproblems don't involve the pivot. This is the case for any node in the recursion tree: if a node corresponds to an array of length $m$, then its two children correspond to arrays of lengths $m_1,m_2$ where $m_1 + m_2 = m-1$. In particular, if a certain level has $x$ nodes then the sum of lengths at that level $S$ and the sum of lengths at the next level $T$ satisfies $S = T + x$; the $x$ pivots disappear from the recursion.

Denote by $N_i$ the number of nodes at depth $i$, and by $S_i$ the sum of lengths at depth $i$. Assuming we start counting at level 0, we have $S_0 = n$, $S_{i+1} = S_i - N_i$, and $N_i \leq 2^i$. You can prove by induction that
$$
 S_i \geq n - (2^i-1).
$$
In particular, $S_{\log_2 n} \geq 1$ (assuming $n$ is a power of 2), so there are at least $\log_2 n$ levels of recursion. Furthermore,
$$
\sum_{i=0}^{\log_2 n} S_i \geq \sum_{i=0}^{\log_2 n} (n+1-2^i) = (n+1)\log_2 n - (2n-1) = \Omega(n\log n).
$$
Since $\sum_{i=0}^\infty S_i$ is exactly the running time of quicksort (up to constants), we see that quicksort always takes at least $\Omega(n\log n)$.


scale-free networks and adjacency matrix Given a distribution over graphs with $n$ nodes having the "scale-free" property, I would like to compute for a pair of vertices $(a,b)$ the probability that they are connected (or more precisely the probability that there is a directed edge from $a$ to $b$).

Is it possible to have such probability distribution ?

Note that the case without the "scale-free" property is not a problem. I can define the probability of having an edge from $a$ to $b$ as $P((a,b))=1/2$ for all $a, b$, $a \neq b$ in the graph.

Thank you.

The most popular generative model for scale-free networks is the preferential attachment model of Barabási and Albert. A graph is sampled using an iterative procedure. This is a different sampling procedure than you suggest, since the goal is not only to generate a certain degree sequence, but also to mimic other properties of real-life networks.

If all you're after is a certain degree sequence, you can use MCMC methods; see for example Stanton and Pinar. Such algorithms don't conform to your type of algorithm, however. If you want to use your type of model, you have to decide in advance which vertices will have high degree and which will have low degree, since otherwise you will get a degree distribution which is either roughly Gaussian or roughly Poisson, but definitely no power law.

If all you're after is a certain degree sequence and you really want to use your own generative model, here is one possibility. Use the preferential attachment model, the algorithm of Stanton and Pinar, or any other randomized algorithm to generate a graph $G$. Now your model is: given two vertices $x,y$, if $(x,y) \in G$ then connect $x$ and $y$ with probability $1$, otherwise connect them with probability $0$.


An obvious approach to explaining NP != coNP, how far has it been pushed? A recent question made me think about an obvious approach for circumventing the "algorithm is allowed to do anything" problem, when proving lower bounds. Instead of starting with a simple looking NP-complete problem, start with a powerful looking logical deduction system.

Then try to find a reasonable general term expression problem, such that equality of the terms can be decided by the logical deduction system, and inequality of the term expressions is NP-complete. (For example, Boolean algebra term expressions would work.) Then start to prove that the logical deduction system cannot efficiently prove equality of specific term instances, unless it has access to specific higher order features, like the cut-rule.

And then the goal would be to push up the required higher orders features as far as possible, i.e. beyond the cut-rule towards fully impredicative higher order logic. But already proving that you need the cut-rule would seem like a nice achievement. How far has such an approach to explaining NP!=coNP actually been pushed in the past?

Not very far. The approach that you are describing is known as proof complexity, and it is covered by several surveys and lecture notes. There are several kinds of proof system being considered:

Frege systems. These are systems in which a proof consists of a sequence of formulas or circuits (depending on the system), and there is a fixed set of derivation rules.
Algebraic proof systems such as the Polynomial Calculus and Nullstellensatz. Here each line is a polynomial.
Cutting planes, in which each line is a linear inequality.

There are also other proof systems such as the Hajos calculus, a proof system for proving that a graph isn't 3-colorable.

We have strong lower bounds for some of these systems, but in the Frege front, the best lower bound is for bounded depth Frege, in which the depth of all lines in the proof is bounded by some constant. This lower bound is similar in some regards to AC0 lower bounds for circuits, but is otherwise more complicated. We have no lower bound for the version in which the depth is bounded but we allow mod $p$ gates; the algebraic methods used to prove lower bounds on circuits don't seem to work, and the problem seems related to derandomizing polynomial identity testing, a notoriously difficult problem in algebraic complexity theory.

The Frege proof system itself has as lines arbitrary formulas, and Extended Frege has arbitrary circuits as lines. It is thought that Extended Frege is stronger than Frege. Other proof systems are conjectured to be stronger than even Extended Frege. It is not clear currently whether there is a "super" proof system, which is optimal up to polynomial factors compared to any proof system. Thus even if we do manage to prove lower bounds for progressively more general proof systems – which is expected to be harder than proving corresponding circuit lower bounds – we wouldn't necessarily be able to prove that NP is different from coNP in this way.


Can every two languages in $RE$ be reduced? If $L_1,\, L_2 \in RE / R$, must there exist a (computable) many-one reduction between them?

I can prove that for every two languages in $R$ exists a reduction between them. A possible reduction $L_3 \leq L_4$ where $L_3,\, L_4\in R$ goes as follows:

given an input $x$ to $L_3$, run $M_3$ (it's TM), if it accepted, return an input that is in $L_4$. Else, return one that isn't (this works assuming $L_4\neq \emptyset,\, \Sigma^*$).

The above idea will not work in $RE$ because $M_3$ might not halt.

Is there a different way to construct a reduction $L_1\leq L_2$ where it us known that $L_1,\, L_2\in RE / R$?  Or is such a general reduction something that cannot be always achieved?

Consider the case $L_2 = \emptyset$. This language is clearly recursively enumerable, but the only language which can be reduced to it is itself.

What is true, and follows directly from the definition, that two RE-complete languages reduce to one another.


Efficient compression of unlabeled trees Consider unlabeled, rooted binary trees. We can compress such trees: whenever there are pointers to subtrees $T$ and $T'$ with $T = T'$ (interpreting $=$ as structural equality), we store (w.l.o.g.) $T$ and replace all pointers to $T'$ with pointers to $T$. See uli's answer for an example.

Give an algorithm that takes a tree in the above sense as input and computes the (minimal) number of nodes that remain after compression. The algorithm should run in time $\cal{O}(n\log n)$ (in the uniform cost model) with $n$ the number of nodes in the input.

This has been an exam question and I have not been able to come up with a nice solution, nor have I seen one.

Yes, you can perform this compression in $O(n \log n)$ time, but it is not easy :) We first make some observations and then present the algorithm. We assume the tree is initially not compressed - this is not really needed but makes analysis easier.

Firstly, we characterize 'structural equality' inductively. Let $T$ and $T'$ be two (sub)trees. If $T$ and $T'$ are both the null trees (having no vertices at all), they are structurally equivalent. If $T$ and $T'$ are both not null trees, then they are structurally equivalent iff their left children are structurally equivalent and their right children are structurally equivalent. 'Structural equivalence' is the minimal fixed point over these definitions.

For example, any two leaf nodes are structurally equivalent, as they both have the null trees as both their children, which are structurally equivalent.

As it is rather annoying to say 'their left children are structurally equivalent and so are their right children', we will often say 'their children are structurally equivalent' and intend the same. Also note we sometimes say 'this vertex' when we mean 'the subtree rooted at this vertex'.

The above definition immediately gives us a hint how to perform the compression: if we know the structural equivalence of all subtrees with depth at most $d$, then we can easily compute the structural equivalence of the subtrees with depth $d+1$. We do have to do this computation in a smart way to avoid a $O(n^2)$ running time.

The algorithm will assign identifiers to every vertex during its execution. An identifier is a number in the set $\{ 1, 2, 3, \dots, n \}$. Identifiers are unique and never change: we therefore assume we set some (global) variable to 1 at the start of the algorithm, and every time we assign an identifier to some vertex, we assign the current value of that variable to the vertex and increment the value of that variable.

We first transform the input tree into (at most $n$) lists containing vertices of equal depth, together with a pointer to their parent. This is easily done in $O(n)$ time.

We first compress all the leaves (we can find these leaves in the list with vertices of depth 0) into a single vertex. We assign this vertex an identifier. Compression of two vertices is done by redirecting the parent of either vertex to point to the other vertex instead.

We make two observations: firstly, any vertex has children of strictly smaller depth, and secondly, if we have performed compression on all vertices of depth smaller than $d$ (and have given them identifiers), then two vertices of depth $d$ are structurally equivalent and can be compressed iff the identifiers of their children coincide. This last observation follows from the following argument: two vertices are structurally equivalent iff their children are structurally equivalent, and after compression this means their pointers are pointing to the same children, which in turn means the identifiers of their children are equal.

We iterate through all the lists with nodes of equal depth from small depth to large depth. For every level we create a list of integer pairs, where every pair corresponds to the identifiers of the children of some vertex on that level. We have that two vertices in that level are structurally equivalent iff their corresponding integer pairs are equal. Using lexicographic ordering, we can sort these and obtain the sets of integer pairs that are equal. We compress these sets to single vertices as above and give them identifiers.

The above observations prove that this approach works and results in the compressed tree. The total running time is $O(n)$ plus the time needed to sort the lists we create. As the total number of integer pairs we create is $n$, this gives us that the total running time is $O(n \log n)$, as required. Counting how many nodes we have left at the end of the procedure is trivial (just look at how many identifiers we have handed out).


How to understand equivalence of indexes of a family of types that are not definitionally equal So I've been reading things about HoTT and trying to get solid on the foundations before getting too much further into the book. I am confused by a certain point; maybe I just haven't read far enough yet however. I don't think my question is specific to HoTT but just dependent type theory in general.

Say you have a family of types defined by something like $B : Nat \to Set$. There are two fibers/indexed types defined by $B(x + y)$ and $B(y + x)$. These are definitely not definitionally equivalent but maybe they are extensionally equivalent because $x + y = y + x$. However I thought that perhaps indexes behave definitionally in some cases in which case $B(x + y)$ and $B(y + x)$ might be extensionally distinct.

I tried thinking about the case of $Fin : Nat \to Set$ (the integers less than a certain value). I think that both $Fin (x + y)$ and $Fin (y + x)$ have no inhabitants however because the standard constructors for them have no constructors that unify with $x + y$ or $y + x$. So they both have no inhabitants but what does that mean about their equivalence? This seemed like a bad case to think about to me.

My main question is the following: how does one think about the equivalence between these two types?

My subquestions/confusions are: Do these types have the same inhabitants? Are they extensionally equal? Does having the same inhabitants means that types are extensionally equal?

We can prove (x : Nat) (y : Nat) -> x + y = y + x (they are propositionally equal). I'm using Agda-ish notation here rather than the notation in the HoTT book because type setting is hard. Note that we can prove this in standard intensional type theory. This gives a function from Nat to Nat to a proof of equality.

In intensional type theory we don't distinguish between types up to judgmental equality. Almost as though there's a rule

     A ≡ B  a : A
     ------------
        a : B

Remember that FZ : Fin 1, Since 0 + 1 ≡ 1, this means that FZ : Fin (0 + 1). If we didn't have a rule like this, it'd be kinda pointless to have computation in our types because the minute we actually have some interesting expression in our type we couldn't witness it.

It's important to keep the different types of equality separate in type theory

Judgmental equality (a judgement) is something actually embedded in the system. You can't touch it when writing programs but it says that two terms are equal if they have the same value more or less
Proposition equality (a proposition) is what we can prove as a programmer. There is one way to prove A = B in standard ITT, with refl : A = A. This means that we can prove A = B if and only if A and B are judgmentally equal.

Whether Fin (x + y) or Fin (y + x) for some x and y have members is dependent on what x and y. If x and y are 0, then Fin (x + y) is judgmentally equal to Fin 0, which is unoccupied.

We can prove that Fin (x + y) = Fin (y + x) though in standard ITT, the proof in a system like Agda looks like

eq : (x y : ℕ) → Fin (x + y) ≡ Fin (y + x)
eq x y rewrite +-comm x y = refl

So in answer to your question, the two types are propositionally equal using an intensional notion of equality. This isn't enough to say if e : Fin (x + y) then e : Fin (y + x), for that we'd need judgmental equality. We can easily construct invertible maps between the two though by pattern matching on the result of eq for example.

Finally, in answer to your last question. In extensional type theory this is the case, in intensional type theory we need some extra tools. HoTT in particular provides us with univalence which is even more flexible: two types can be propositionally equivalent if they're isomorphic.


3SAT with an oracle for expanding the clauses Let's consider 3SAT, so we have clauses like:

(A or B or C) and (A or not B or D) and ...

If we distribute the "and" over the first two clauses, we get the disjunction of:

      A and A --> simplifies to A

      A and not B

      A and D

      B and A

      B and not B --> simplifies to false

      B and D

      C and A

      C and not B

      C and D

I presume the brute force strategy of expanding all the clauses and simplifying when possible would take exponential time.  My question: what if an oracle gives you a certificate telling you which clauses to expand?  Is it known whether this could get you down to polynomial time?

Let's call this language 3SAT^A, so it's something like:
3SAT^A = {(x, A(x)) : x is a 3SAT formula}, where A(x) tells you how to expand the clauses in x.

Is it known whether there is an A such that 3SAT^A is in P?  If so, could one hope to show P != NP by showing that no such A is computable in polynomial time?

Your question seems closely related to the question of whether $NP=coNP$. It seems that the existence of such an oracle would imply $NP=coNP$ since the oracle would give you a polynomial certificate for "no"-instances of $SAT$.

I don't think this would be a viable way to show $P\not = NP$ since all you'd be showing is that there's no way to expand clauses in polynomial time, but that does not rule out other approaches for solving $SAT$.


Time complexity of an algorithm: Is it important to state the base of the logarithm? Since there is only a constant between bases of logarithms, isn't it just alright to write $f(n) = \Omega(\log{n})$, as opposed to $\Omega(\log_2{n})$, or whatever the base might be?

It depends where the logarithm is. If it is just a factor, then it doesn't make a difference, because big-O or $\theta$ allows you to multiply by any constant.

If you take $O(2^{\log n})$ then the base is important. In base 2 you would have just $O(n)$, in base 10 it's about $O(n^{0.3010})$.


How multiprocessing is done in Single Core Systems? Can we do multiprocessing on single core system ? I thought that single core means that ONLY one process/thread can execute at any time. For multiple processes , there can be concurrent execution to appear as they are executing Simultaneously.

The operating system (or the thread scheduler) switches from one thread to another at more or less regular intervals, making it look as if these threads were running simultaneously.


Prove the Droid Trader Problem is NP-complete This question is from chapter 8, exercise 35, of Algorithm Design by Kleinberg and Tardos.

A player in the game controls a spaceship and is trying to make money
buying and selling droids on different planets. There are $n$
different types of droids and $k$ different planets. Each planet $p$
has the following properties: there are $s(j, p) \geq 0$ droids of
type $j$ available for sale, at a fixed price of $x(j, p) \geq 0$
each, for $j = 1, 2, \dots , n$, and there is a demand for $d(j, p) \geq 0$ droids of type $j$, at a fixed price of $y(j, p) \geq 0$ each.
(We will assume that a planet does not simultaneously have both a
positive supply and a positive demand for a single type of droid; so
for each $j$, at least one of $s(j, p)$ or $d(j, p)$ is equal to $0$.)
The player begins on planet $s$ with $z$ units of money and must end
at planet $t$; there is a directed acyclic graph $G$ on the set of
planets, such that $s$-$t$ paths in $G$ correspond to valid routes by
the player. (G is chosen to be acyclic to prevent arbitrarily long
games.) For a given $s$-$t$ path $P$ in $G$, the player can engage in
transactions as follows. Whenever the player arrives at a planet $p$
on the path $P$, she can buy up to $s(j, p)$ droids of type $j$ for
$x(j, p)$ units of money each (provided she has sufficient money on
hand) and/or sell up to $d(j, p)$ droids of type $j$ for $y(j, p)$
units of money (so I'm assuming you can make multiple buy/sells at
each planet). The player’s final score is the total amount of money
she has on hand when she arrives at planet $t$.

I'm trying to prove this problem is harder than some NP-complete problem, but I am quite stuck. Since the planets are organized in a DAG, I think the 'hardness' of the problem comes from the fact that you can buy and sell many different types of droids at each planet. Also, this problem is a maximation problem, and I don't know many NP-complete maximization problems other than quadratic assignment.
My thought process is that the droids have to represent something, for example choosing vertices of a graph. Then the price of the droid reflects the 'value' in some way; for example in a vertex cover reduction, the droid representing vertex $i$ would have a sale price equal to the degree of vertex $i$ for example.
Something that worked well for me for the previous 30 exercises was to consider a very simple version of the problem. So in this case, I considered cases where the planets were just a line graph, or there are only two types of droids, or each planets sells exactly 1 type of droid and buys 1 type of droid (so you can force the player to buy/sell instead of just holding on to their cash). I try to simplify in this way and see if it starts to resemble other NP-hard problems, which is why I suspect that it should be a vertex-cover or 3-sat reduction.
Any hints would be appreciated such as what problem X should I choose to reduce to Droid Trader Problem, or how should I view this problem (e.g. 3-SAT can be viewed as choosing one out of $2^n$ choices and then checking that the choice satisfies some set of contraints)

You can find a simple reduction from Knapsack or from the Partition Problem (which itself reduces to Knapsack).

Let's do it from the Partition Problem:

  Given $n$ integers $S = \{a_1, a_2\ldots, a_n\}$ with even total sum, does there exist a subset whose sum is exactly half the sum of all elements ?

So suppose you are given an instance of the Partition Problem. We construct an instance of the Droid Trader problem as follows:

There will be $n$ types of droids, one for each integer in $S$. There will be two planets $s$ and $t$, with a directed edge from $s$ to $t$.
On planet $s$, the player can buy a single droid of each type $i$ for a price of $a_i$, and can sell nothing.
On planet $t$, the player can sell droids of every type $i$ for a price of $2\cdot a_i$, and can buy nothing.
The player starts with $z$ equal to half the sum of all elements in $S$.

Then, it is easy to see that, the player can never end up with more money than $\sum S$. Moreover, he can achieve $\sum S$ if and only if he can buy $\frac{1}{2}\sum S$ worth of droids on the first planet, i.e. there exists a subset of $S$ with sum $\frac{1}{2}\sum S$.

So the original question on the Partition Problem instance is equivalent to asking if the player can end up with $\sum S$ money in the corresponding Droid Trader problem.

Because this is a polynomial time reduction, this proves the claim.


Minimal colouring problem aproximation threshold Given that 3-colouring and 4-colouring are NP-complete show that the
  aproximation threshold of the minimal colouring problem is greater or
  equal than $\frac{4}{3}$.

My current approach is to work by contradiction assuming there was such an algorithm that in polynomial time can produce a $\delta$-aproximation with $\delta < \frac{4}{3}$ using the fact that 3-colouring and 4-colouring are NP-complete. I didn't obtain much progress.

References

I just wanted to point out that this is an application of the "Gap technique" presented in the book "Complexity and Aproximation" of Auseillo et alii., I wasn't familiar with the notation they use so I couldn't understand how to fully apply the technique.

Consider 3-coloring and suppose that a $\delta$-approximation algorithm $A$ for the minimum coloring problem with $\delta < \frac{4}{3}$ exists.

Let $G$ be the input graph and $x$ be the solution returned by $A$.

If $G$ is 3-colorable then $A$ would return $3$.
In fact, $x \lt 4$ since $A$ would return a solution $x \lt \ ( 3\cdot \delta)=3* \frac{4}{3}=4$ by hypothesis.
If $G$ is not 3 colorable then $A$ would return $x \geq 4$ since $G$ needs at least $4$ colors.

Hence, with $A$ you would be able to determine whether $G$ is 3 colorable or not.

But 3-Coloring is NP-Complete (contradiction).


On the minimum order of a maximal independent set in cycle graphs and path graphs I can see from this question that a $K_{r + 1}$-free graph with $n$ vertices and $e$ edges contains an independent set of order at least
$$\frac{n}{2e/n + 1} \tag{1} $$
Since for a $C_{n}$/$P_{n}$ we know how many edges it contains it is easy to determine (1).

However, are there any particularities of cycle graphs and path graphs that would allow me, for such a graph $G$, to determine exactly $\min\{\mathopen|A\mathclose| : A\text{ is a maximal independent set of } G\}$, i.e. the minimum number of vertices that a maximal independent set of $G$ must contain.

The smallest maximal independent set in a cycle or path of length $n$ clearly has size about $n/3$. This can be seen by inspection and certainly doesn't need anything like Turán's theorem.


Does Types and Programming Languages use a recursive equation to define a recursive type or its generator? In Types and Programming Languages by Pierce et al:

  The recursive equation specifying the type of lists of numbers is similar to the equation specifying the recursive factorial function on page 52:

factorial = λn. if n=0 then 1 else n * factorial(n-1)

  Here, as there, it is convenient to make this equation into a proper deﬁnition by moving the “loop” over to the right-hand side of the =.
  We do this by introducing an explicit recursion operator µ for types:

NatList = µX. <nil:Unit, cons:{Nat,X}>;

  Intuitively, this deﬁnition is read, “Let NatList be the inﬁnite type satisfying
  the equation X = <nil:Unit, cons:{Nat,X}>.”

I have some questions for understanding it:

What does the “loop”  mean?
Does the recursion operator µ for types play similar role as operator λ for abstractions?
Doesn't NatList defined by NatList = µX. <nil:Unit, cons:{Nat,X}> look more like the generator of the recursive type X, i.e. a type mapping so that X = NatList X?
How can NatList as the generator of the recursive type X be the inﬁnite type X satisfying the equation X = <nil:Unit, cons:{Nat,X}>?

Thanks.

You've stumbled across the difference between isorecursive and equirecursive types.

Equi-recursive types say "types are (possibly) infinite trees, and a recursive type is the solution to a recursive equation". Specifically, $\mu x\ldotp T = [\mu x \ldotp T/x]T$. These are conceptually simple, but in practice difficult to work with, since deciding whether two types are equal (or worse, subtypes of one another) or not is tricky.

Conversely, isorecursive types say that recursive types are just syntax. You are allowed to unroll them according to the equation above, but $\mu x\ldotp T$ and $ [\mu x \ldotp T/x]T$ are fundamentally different types, and must use the explicit fold and unfold instructions.

If you keep reading Pierce, he will explain this in the book.

Answering your specific questions:

The "loop" is that the definition on the RHS or the = is allowed to reference the name defined on the left. This is awkward for theory, because we don't want to treat top-level definitions as special.
Yes, $\mu$ is similar to $\lambda$ in the sense that they both bind variables. However, it's different in that there's always a very specific thing that gets plugged in for the bound variable with $\mu$, whereas $\lambda$ is useful precisely because we can plug the variable with anything. Also, the bound variable of $\mu$ denotes a type, whereas with $\lambda$ it denotes a term.
Yes, and that's the point of the $\mu$ operator. It says "I am the syntax that takes the generator for a type, and turns it into an actual type you can use like any other type in your program." And it make explicit the role of $X$ in the equation your outline.
Again, this is the job of $\mu$ by definintion. It is the piece of syntax that says "given the generator, tie the knot and make it an actual type."

The thing is, you can't really understand $\mu$-types on their own. Otherwise it's just syntax. The key is in the type rules for $\mu$ types. For isorecursive types, there are fold and unfold rules that allow us to "run the generator" one step. For equirecursive types, there are special rules in how type equality is determined that allow us to treat $\mu x \ldotp T$ as actually being the solution generated by the recurrence equation. But, these type rules will change depending on the specific language or calculus you're using.


Ordering of operations in a DAG of git commits Context: I'm looking for a better state resolution algorithm for https://github.com/MichaelMure/git-bug
Summary of the current algorithm and shortcomings
git-bug is a distributed bug-tracker that embed in git, the distributed version control system. To do so, bugs are stored in the native git data structure (commits and branches). Each bug has its own branch and adding commits to it will evolve the bug state. This allows using git as both a database and a transport, in the sense that users can push/pull those branches to distributes updates and collaborate with each other.
More details can be found in this document: https://github.com/MichaelMure/git-bug/blob/master/doc/model.md
Now to deal with the distributed nature of this system and allow merges, the state of a bug can't be stored as-is. Instead, it's stored as an ordered series of operations: adding a comment, changing the title ... When reading a bug, the final state is "compiled" by applying those operations in order to an originally empty state.
I believe (but don't quote me on that) that this is a form of Operational Transformation (OT).
In reality, multiple operations can be stored in a single git commit but for the purpose of this conversation, let's assume that one git commit stores exactly one operation.
To make my life a bit easier at the beginning of this project, I reduced the complexity of this problem by imposing that the series of commit holding the operations would have to be linear, which make the ordering of the operations trivial: the order of the commit implies the order of the operations.
This purely linear restriction has a major implication: when fusing[1] together with two git DAG when doing a git pull, the equivalent of a git rebase has to be used. The commits of one diverging branch are reapplied on top of the other, which means that the data structure is not actually immutable. Not only this is problematic if commits are signed, but I'm also suspecting this can prevent the commits to reach a stable ordering when there is no central server acting as "source of truth". If three users A, B, and C are pulling and rebasing commits in a cycle A->B->C->A, I suspect they will never reach a stable ordering.
Another way to do things would be to use the equivalent of git merge: the diverging branches are fused together with a new commit having both branches as parents and we end up with a DAG. Although and this is important, in the normal git behavior this merge commit holds the fused state. For git-bug, each operation is disconnected from the others, so the merge commit would hold no fused state, just that the branches fused.
The actual question
I'm looking for an algorithm capable of doing this ordering of commits in a git DAG using git merge, in the most stable way possible.

using git merge: git merges are allowed, possibly rebase as well if necessary
most stable way possible: in a perfect world, the operations should be ordered by their real-time creation. Obviously, this is not fully possible in a distributed system, so the goal is to get a logical order as close as possible, despite concurrent editions and merges. Thankfully, bugs in a bug-tracker are slightly malleable and will retain the user's intent even if the ordering is slightly wrong.

As you may have guessed, I'm a bit out of my depth here so, short of an actual algorithm, any pointers for theoretical ground or possible solutions would be helpful.
Things I considered

storing in each operation/commit the reference of the ancestor at the time of the creation
using some form of logical clock, stored in each commit
some sort of topological ordering
a combination of those?

[1]: I'm avoiding "merge" here to avoid confusion, it's not the git merge.

What exactly is an operation in your model?  If two concurrent operations commute, then any topological sort of your DAG will give the same result (cf. Strong Eventual Consistency).  If two concurrent operations are independent of one another it's likely they commute (or can be made to commute); otherwise, if there is a deterministic way to prioritise them, then do that (as in CRDTs).  I can't be more specific without understanding what an operation is.


lower bound of checking if in array are two different elements Considering the lower limit to the problem of checking whether the array are only the same number via comparisons. And thnik about $ n-1 $.
Consider the diagram hasse. This diagram must be consistent (one piece), so you need at least $ n-1 $ edges (comparisons),.

However, I would like to consider a decision tree. Unfortunately, I can not consider this, look how I think about it.

Decision tree lower bounds don't quite work here. The obvious way to apply a decision tree lower bound is to consider the output of the algorithm, which is either TRUE or FALSE. Since there are two possible outputs, the decision tree lower bound gives a lower bound of one comparison. Not very helpful.

A more interesting example of the decision tree technique forces the algorithm to output a little more, namely either it outputs YES (all the elements are the same), or a pair of different elements (represented as their indices). You can argue that whenever the algorithm returns NO it actually knows two elements which are different. Considering all inputs of the form $x_1 = \cdots = x_{i-1} = x_{i+1} = \cdots = x_n = 0, x_i = 1$, we see that for each $i$ there must be a leaf of the form $(i,\ast)$. This means that there must be at least $n/2$ NO leaves, resulting in a lower bound of $\log_2(1+n/2)$ on the number of comparisons. This can plausibly be improved to $\log_2(1+\binom{n}{2})$, but both quantities are $\Theta(\log n)$.

The correct way to argue here is using an adversary argument. Consider any algorithm, and trace its execution, always answering YES to any query. Consider the graph whose vertices are all elements (i.e., all indices), and the edges correspond to queries performed by the algorithm. If the graph is not connected, the algorithm can't know whether all elements are the same (indeed, it is consistent both that all elements have the value $0$, or that the elements in the $i$th connected components have the value $i$). Since a connected graph has at least $n-1$ edges, any algorithm must perform as least $n-1$ comparisons. It's not hard to see that this bound is achievable.


Recalculating shortest path after changing the weights I have a weighted, directed graph. I do the following. Given nodes $s$ and $t$ I compute shortest path. Then, I decrease weights of some edges and want to see if there is now another shortest path. Of course, I can recompute shortest path, but I want something faster.

For example, one approach would be to store shortest paths from $s$ to $t$ for every edge in the graph. Then, when I change the weights it takes constant time to check if the shortest path changed (even though, the first step takes much more time). The drawback is that I have to store many paths and to calculate all simple paths in advance, so I'm seeking for alternatives.

So my question is if it's possible to check if the shortest path changed after we decrease edge weights?

Edit: Apparently, this is a problem of dynamic graphs. I didn't delve into the algorithms, so, which algorithm can I use for this problem? I want to improve on running time Dijkstra algorithm.

The standard term for this kind of problem is "dynamic shortest paths" or "shortest paths in a dynamic graph".  Here "dynamic" refers to the fact that the graph might be updated, and you want to update the shortest-paths information (hopefully more efficiently than re-computing it from scratch).  There are many kinds of updates to the graph one can consider: deleting a vertex, inserting a vertex, deleting an edge, inserting an edge, increasing the length of an edge, decreasing the length of an edge.  Your problem is the special case where we only have to deal with decreases to edge weights.

So, I suggest you search the research literature (e.g., using Google Scholar).  You should find a bunch of papers that discuss algorithms for this situation.


How is a grammatical rule applied if the variable is not part of the source word I'm currently working with this grammar:

$S \to aSBC$
$S \to aBC$
$CB \to BC$
$aB \to ab$
$bB \to bb$
$bC \to bc$
$cC \to cc$

It is supposed to define the language $$ L = \{a^nb^nc^n : n \geq 1\}. $$

I need to know how to get through the grammar rules to end up with $L$. So I started with the first two rules which end up to be $a^n(BC)^n$.

$$ S \Rightarrow^* a^{n-1}S(BC)^{n-1} \Rightarrow a^{n-1} aBC (BC)^{n-1} = a^n (BC)^n.$$

It's quite obvious until there. My lecture than adds the third rule to $a^n(BC)^n$:

$$ a^n(BC)^n \Rightarrow^* a^nB^nC^n. $$

And that's where I'm completely lost. How is the third rule applied if its left-hand side ($CB$) isn't even part of the initial word ($a^n(BC)^n$)?

When we write $a^n(BC)^n$, we mean the word composed of $n$ copies of $a$ followed by $n$ copies of $BC$; using $^n$ is just a shortcut. For example, $a^2(BC)^2$ is shortcut for the word $aaBCBC$. Indeed, $^n$ just doesn't belong to the syntax of words, which states that a word is a sequence of terminals and non-terminals.


What does this language notation specify? I am given this exercise:
Let L1 ={akbk : k > 0} and L2={ck : k > 0}. For each of the following strings wi, state and explain whether or not wi ∈ L1L2.
w1=ε
w2=aabbcc
w3=abbccw
w4=aabbcccc
w5=ccaabb
w6=ab
So far I haven't seen such a notation for languages as the one that L1 and L2 are seen in. For example, I had seen other notations such as: L1={w∈{a,b}∗: every a in w is immediately preceded and followed by a b} which I could understand. A parallel between the two notations will be much appreciated.
Moreover, what does it refer by L1L2? Is this counted as a union or a concatenation?
What I could figure out from this exercise is what w1 is surely not in L1L2, as k must be over 1. Following the same logic, the other answer would be w2 as k will always be the same in both L1 and L2, hence the number of a's, b's and c's shouldn't differ.
Is the above thought correct or is it more to this notation than I have already thought of?

Language concatenation is defined as follows:
$$
L_1 L_2 = \{ w_1 w_2 : w_1 \in L_1, w_2 \in L_2 \}.
$$
In other words, a word $w$ belongs to $L_1 L_2$ if it can be written as the concatenation of two words, $w_1 \in L_1$ and $w_2 \in L_2$.
This definition should suffice for solving the exercise.


Relational query for universally quantified formula My university is participating in the implementation of a library borrowing managing system at Richelieu National Library in France.

I received the order to formulate the query: "find all users having borrowed every book" in relational Algebra, in relational Calculus and in SQL (which would probably not happen, probably librarians want to test the limits of the database).

The database has the following pattern (the primary keys are in bold):

Borrowing(People, Book, DateBorrowing, ExpectedReturnDate, EffectiveReturnDate)
Lateness(People, Book, DateBorrowing, LatenessFee)

I tried

$$\Pi_{People}(Borrowing)\div\Pi_{People}(\sigma_{Book} (Borrowing))$$

But It seemed to be wrong as far as to do  $r\div s$, $S\subseteq R$  is needed, which seems not to be the case, but why? I'm still talking about people, isn't it?

I then tried the following relational calculus formula:

$$\{t.People|Borrowing(t)\wedge(\forall u Borrowing(u)\Rightarrow t.DateBorrowing)\}$$

To find every books that have a borrowing date. I know this calcuation is false but I don't know how to do better...

Then in SQL:

SELECT People FROM Borrowing
    WHERE FORALL Books EXISTS DateBorrowing

That is what I tried and I know that is not the right way to "find all users having borrowed every book". Can you help me expressing correctely such a querry?

SQL does not have a universal quantifier, but an equivalent can be constructed from the existential one, through a normalization process similar to Skolemization: $$\forall x P(x) \iff \nexists x \neg P(x)$$

In your case, you want the users for which there does not exist a book that they have not borrowed:

select * from people p
where not exists
  (select * from books b
   where b.id not in
     (select book_id
      from borrowings
      where people_id=p.id)
  )

(Note that I have assumed tables for people and books to represent their existence separately from the borrowings table, which, for instance, may be empty at the inception of the system.)


Book recommendations on the analysis of randomized algorithms I would like to read some books (or any other material) that cover the design of randomized algorithms with a particular focus on the analysis. My main goal is to develop the rigour needed to construct the proof of correctness for such algorithms.
I am currently reading Probability and Computing - M. Mitzenmacher, E. Upfal, which I find to be a good introduction to this topic.
What are your suggestions?

Randomized Algorithms by Motwani, Rajeev, and Raghavan contains a lot of excellent material on the design and analysis of algorithms.  They show many proofs of correctness for different randomized algorithms.