Addition of 3 bits using Full Adder when the initial carry bit is 0 How do I add 3 bits using full adder and basic gates, when the initial carry bit is 0??

I have tried using two full adders where two terminals of the first adder gets the first two inputs then the output of this adder goes to of the inputs of the second adder and the third input is given to the second input terminal of the second adder. The carry out from the first adder goes to the carry input of the second adder.

I've added a picture of the circuit which was created by using Logisim(software for designing digital logic circuit).

But it doesn't give the right answer.

normally in binary system, for addition of three bit sum is 1 and carry output bit is 1.

  1+1+1 = 1 & carry bit = 1

But as you can see in the picture of the circuit I designed below, output of my circuit for adding three binary digit, sum is 0 and carry output bit is 1.
 which is not the right answer

  1+1+1, is sum = 0 & carry = 1

The reason of this is clear to me. But I can't design the exact circuit.
How do I design the circuit that can add 3 bit when initial carry is 0?

A full adder adds three bits and outputs a sum and a carry. If you want to add three bits, you just connect them to the inputs x, y, and carry of the full adder.

If for some reason there is a requirement that the carry input of the first full adder must be zero, then you leave that first full adder totally unconnected and connect to the three inputs of the second full adder.


Input size of 3-SAT when analyzing complexity We know that $\text{3-SAT}$ problem is NP-complete, but I am not sure what is meant by size of input. Does this mean number of literals, or number of variables?

At the most basic level, the size of the input is the length of the string that encodes the input given to the Turing Machine - i.e. the number of cells it takes up on the tape under the chosen encoding scheme.

In practice though, we often measure the size of the input via proxy measurements. So for problems like 3-SAT, we might choose the number of variables or the number of clauses as a proxy for the size of the input. Another example is for many graph based problem the number of vertices is chosen as a proxy for the size of the input, even though the length of the encoding of a graph may be something more like $O(|V|^{2}\log|V|)$. Note that this is polynomial in $|V|$, so when we are considering polynomial time algorithms or reductions, the polynomial factor between the proxy and the actual size poses no problem.


"Process functions" in iterative and recursive depth-first search I was reading The Algorithm Design Manual by Steven Skiena, and I noticed his use of "process functions" in depth-first search and breadth-first search. Consider the following pseudocode for depth-first search:

DFS(G,u)
    state[u] = "discovered"
    process_vertex_early(u)
    entry[u] = time
    time = time + 1
    for every vertex v adjacent to u
        if state[v] = "undiscovered"
            parent[v] = u
            process_edge(u,v)
            DFS(G,v)
        else if state[v] != "processed" or G is directed
            process_edge(u,v)
    state[u] = "processed"
    exit[u] = time
    process_vertex_late(u)
    time = time + 1

Notice the use of the process_vertex_early, process_edge, and process_vertex_late functions.

I am attempting to implement an iterative version of depth-first search to avoid a stack overflow with larger graphs. Here is the pseudocode for my attempt:

DFS(G)
    mark every vertex in G as "undiscovered"
    mark the start and finish time for every vertex in G as (0, 0)
    time = 0
    for every vertex vrtx in G
        create empty stack S
        if vrtx is "undiscovered"
            S.push(vrtx)
        while S is not empty
            time = time + 1
            u = S.top
            if u is "undiscovered"
                u.start_time = time
                mark u as "discovered"
                process_vertex_early(u)
            done = true
            for every vertex v adjacent to u
                if v is "undiscovered"
                    done = false
                    v.parent = u
                    process_edge(u,v)
                    S.push(v)
                else if v is not "processed" or G is directed
                    process_edge(u,v)
            if done
                S.pop
                mark u as "processed"
                u.finish_time = time
                process_vertex_late(orig)

I ran both versions of the code for a sample graph of 10 vertices and generated the following data:

Iterative data:
vertex  early   edge    late    s_time  f_time  parent
0       1       1       1       1       18      -1
1       1       1       1       14      14      5
2       1       1       1       13      13      5
3       1       3       1       5       11      7
4       1       3       1       2       17      0
5       1       6       1       3       16      4
6       1       3       1       6       10      3
7       1       3       1       4       12      5
8       1       3       2       8       8       9
9       1       3       1       7       9       6

Recursive data:
vertex  early   edge    late    s_time  f_time  parent
0       1       1       1       1       20      -1
1       1       1       1       14      15      5
2       1       1       1       16      17      5
3       1       2       1       7       10      6
4       1       2       1       2       19      0
5       1       4       1       3       18      4
6       1       2       1       6       11      9
7       1       2       1       8       9       3
8       1       2       1       4       13      5
9       1       2       1       5       12      8

Here is the adjacency list for the graph I used:

0 : 4
1 : 5
2 : 5
3 : 6,7
4 : 0,5
5 : 1,2,4,7,8
6 : 3,9
7 : 3,5
8 : 5,9
9 : 6,8

I know that the vertices will be visited in different orders for the recursive and iterative implementations and that neither order is right or wrong, which is why the values for s_time, f_time and parent are different. The early and late columns represent the number of times each function was called for each vertex, while the edge column represents the number of times the process_edge function was called for each vertex as the u vertex. I feel like these values should be the same for both implementations or at least more similar than they are.

My question is: have I preserved the semantics of the original algorithm with my iterative translation? What changes, if any, should I make?

Here is an iterative algorithm which preserves the behavior of the original recursive algorithm. The idea is to let each vertex to keep track of its next child to visit.

Iterative DFS on G starting at vertex v
    mark every vertex in G as "undiscovered"
    create stack S, each of whose elements will be a pair that consists of a vertex and the index of its next child to visit
    S.push([v,0])
    state[v] = "discovered"
    process_vertex_early(v)

    while S is not empty
        let [v, i] be the top element of S
        if i is less than the number of neighbours of v
            update that element to [v, i+1]
            let w be the i-th neighbour of v
            if w is marked "undiscovered"
                state[w] = "discovered"
                process_vertex_early(w)
                parent[w] = v
                S.push([w, 0])
                process_edge(v, w)
            else if state[w] is not "processed" or G is directed
                process_edge(v,w)
        else
            pop S
            process_vertex_late(v)
            state[v] = "processed"

There are general strategies that convert recursive algorithm/functions to iterative algorithm/functions. You can search "recursion and iteration" for more information if you have not done it yet.


Analysis of and references for Koch-snowflake-like (and other exotic) network topologies In computer networking and high-performance cluster computer design, network topology refers to the design of the way in which nodes are connected by links to form a communication network. Common network topologies include the mesh, torus, ring, star, tree, etc. These topologies can be studied analytically to determine properties related to their expected performance; such characteristics include diameter (maximal distance between a pair of nodes, in terms of the number of links which must be crossed if such nodes communicate), the average distance between nodes (over all pairs of nodes in the network), and the bisection bandwidth (the worst-case bandwidth between two halves of the network). Naturally, other topologies and metrics exist.

Consider a network topology based on the Koch snowflake. The simplest incarnation of such a topology consists of three nodes and three links in a fully-connected setup. The diameter is 1, average distance is 1 (or 2/3, if you include communications inside a node), etc.

The next incarnation of the topology consists of 12 nodes and 15 links. There are three clusters of three nodes fully, each cluster being fully connected by three links. Additionally, there are the three original nodes, connecting the three clusters using six additional links.

In fact, the number of nodes and links in incarnation $k$ are described by the following recurrence relations:
$$N(1) = 3$$
$$L(1) = 3$$
$$N(k+1) = N(k) + 3L(k)$$
$$L(k+1) = 5L(k)$$
Hopefully, the shape of this topology is clear; incarnation $k$ looks like the $k^{th}$ incarnation of the Koch snowflake. (A key difference is that for what I have in mind, I am actually keeping the link between the 1/3 and 2/3 nodes on successive iterations, so that each "triangle" is fully connected and the above recurrence relations hold).

Now for the question:

  Has this network topology been studied, and if so, what is it called? If it has been studied extensively, are there any references? If not, what are the diameter, average distance and bisection bandwidth of this topology? How do these compare to other kinds of topologies, in terms of cost (links) & benefit?

I have heard of a "star of stars" topology, which I think is similar, but not identical, to this. If anything, this seems to be more of a "ring of rings", or something along those lines. Naturally, tweaks could be made to the definition of this topology, and more advanced questions could be asked (for instance, we could assign different bandwidths to links introduced at earlier stages, or discuss scheduling or data placement for such a topology). More generally, I am also interested in any good references for exotic or little-studied network topologies (regardless of practicality).

Again, apologies if this demonstrates ignorance of relevant research results, and any insights are appreciated.

Not really a straight answer, but I don't have the ability to comment yet. I think you are confusing the Koch snowflake with the Sierpinski gasket/triangle. A Koch topology would just be equivalent to a path. The Sierpinski triangle has the properties you describe.

A quick google shows a wealth of papers and webpages on Sierpinski networks, although there is little agreement on the exact topology.


Data structure for selection of K elements and taking sum The problem:

We are given an array $A$, an integer $Z$ and a value $Q$. The goal is to maximize the sum of $A$, by performing following operation any number of times:
We can select exactly $Z$ elements from the given array and perform XOR on each of them with $Q$.

Is there any data structure I can use which can perform this efficiently or any algorithm I am not aware of?

I tried finding each element's maximum possible value (using XOR/ignoring it), sorting the array and then making the selection but it did not work, which leads me to believe that the greedy approach won't work here.

I am primarily looking for an algorithm that can help or a data structure, not necessarily the code.

For example, given the array $[1, 2, 3, 4, 5], Z = 2$ and $Q = 4$, the answer is 23 as I can take XOR of 1 and 2 with 4 and of 3 and 4 with 4 as well.

Edit: The sum 23 is obtained as follows: We need to select Z (2) values at a time. So we select 1 and 2 and obtain their XOR with Q(4), which makes it 5 and 6. We then select 3 and 4 and obtain their XOR with Q, which makes them 7 and 0. Thus the final array becomes $[5,6,7,0,5] which is equal to 23 and is maximum possible sum.

First, note that for any $a$, since XOR is associative:

$$(a \oplus b) \oplus b = a \oplus (b \oplus b)$$

Since $b \oplus b$ is $0$ and $0$ is neutral for XOR, we get that:

$$(a \oplus b) \oplus b = a \oplus (b \oplus b) = a \oplus 0 = a$$

In other words, there is no point performing XOR operation more than twice, for any $a$ with any $Q$. You can either XOR once, or not XOR at all (XOR twice)

Now, suppose you have an array $A$. Prepare the array $B$ as an array of the difference between $A$ before and after we XOR it:

$B_i = \max\{0, A_i \oplus Q - A_i\} $ (Since performing XOR on $A_i$ twice yields $A_i$, we can also choose $A_i$ itself).

Preparing $B$ takes $O(n)$.

Increasing the sum of $A$ is now equivalent to selecting the $Z$ XORS that their sum - difference is greatest, which is equivalent to selecting $Z$ max elements from $B$.

For that, there's a better solution than sorting ($O(n\log n)$):

Select the $Z-th$ largest element of $B$ using selection algorithm
Sweep $B$ and save any element that is larger than the $Z-th$ largest element

The indices of the elments chosen in $B$ determine both the elements of $A$ you select, and the XOR performed (or not performed). In total, it took $O(n)$ time.


Equivalence of NFA and DFA - proof by construction I was looking at the construction proof showing the equivalence of NFA and DFA from Sipser's text. It started by taking number of states of DFA as $\mathcal{P}(Q)$, where $\mathcal{P}(Q)$ is the set of subsets of $Q$.

My doubt is when we construct DFA from NFA, all the subsets may not occur in that DFA. So how could we write that the number of states of DFA constructed is $\mathcal{P}(Q)$.

It is true that this construction may result in a DFA with unreachable states. The general construction begins simply by including all possible states, then adding the appropriate transitions, so typically the resulting DFA won't be the smallest DFA that accepts the same language (in terms of the number of states).

An alternative approach is to only add states as you generate the transitions (rather than adding all states at the start). This will give you only reachable states, but even then, this DFA may not be the smallest possible.

Nonetheless both approaches result in a DFA that accepts the same language as the initial NFA.

Thus given an NFA with $q = |Q|$ states, we can always generate a DFA with $2^{q} = |\mathcal{P}(Q)|$ states that accepts the same language as the NFA.

Generating the minimal DFA is a slightly different question (but we know that it will have no more than $|\mathcal{P}(Q)|$ states).


Linear programming IFF with equality constrain Is it possible to write the following logical constrain in linear programming?

Let $v$ be an integer variable and $k$ an integer constant. Let $y$ be a binary variable. The logical constraint is

$y=1 \Longleftrightarrow v=k$.

I need this kind of constraint in linear programming to use it in AMPL, but I really can't find a way to write it down as a linear constraint.

Yes, this is possible. The main idea is that a binary variable can be used to enable/disable a inequality constraint as follows: given an inequality $a\cdot x\leq b$ and a binary variable $v$, pick a constant $L$ such that $a\cdot x - b\leq L$ is true for all variable assignments. Then the inequality $a\cdot x \leq b+ (1-v)L$ will be equal to $a\cdot x\leq b$ if $v=1$ and will always be true if $v=0$.

So, the constraint $y=1\Rightarrow v=k$ part can be modeled by the two inequalities $v\leq k+(1-y)L$ and $v\geq k - (1-y)L$. For the other part, $v=k\Rightarrow y=1$, we first transform this into $y\neq 1\Rightarrow v\neq k$. We can model the $v\neq k$ condition as $v < k \vee v > k$ and to model the 'or' we introduce a new binary variable $q$. In particular, we want $v<k$ if $q=1$ and $y=0$ and $v>k$ if $q=0$ and $y=0$, so we get $v < k + (1-q+y)L$ and $v > k-(q+y)L$.

In summary, the inequalities $$\begin{align} v&\leq k+(1-y)L\\ v&\geq k - (1-y)L\\ v &< k + (1-q+y)L\\  v &> k-(q+y)L\end{align}$$ model the constraint $y=1 \Leftrightarrow v=k$.


What are some interesting applications of the skyline problem? You are given a set of $n$ rectangles in no particular order. They have varying widths and heights, but their bottom edges are collinear, so that they look like buildings on a skyline. For each rectangle, you’re given the $x$ position of the left edge, the $x$ position of the right edge, and the height. Your task is to draw an outline around the set of rectangles so that you can see what the skyline would look like when silhouetted at night.
Source

Drawing in practice I imagine can come in different forms, for example if a building is described by a triple (leftX, height, rightX) then the output can be a left to right ordered list $\{x_{1},h_{1},x_{2},h_{2},x_{3},h_{3},x_{4},h_{4},...\}$ where each $x_{i}$ represents a vertical edge and each $h_{i}$ represents a horizontal edge.

This problem is clearly defined and there are some quite efficient algorithmic solutions, however I could not find anywhere the motivation for this problem. Why would anyone want to solve it? Are there any interesting applications where being able to solve this problem efficiently is important?

The "skyline problem" is an example of finding the Pareto front of a set of points in 2-D space. More generally it's an example of multi-objective optimization which has many applications.

You might find this thread relevant.


Difference between a lambda term and a lambda expression Is there any difference between a $\lambda$-term and a $\lambda$-expression?

Looking at the recursive definitions on Wikipedia of
$\lambda$-term and $\lambda$-expression, they are equivalent. But I am confused as they are slightly different and refer to what they define by a different name.

Books on lambda calculus define only lambda terms. Some programming languages may call anonymous function lambda expressions.


What is the time complexity of the below code? i=12

while( i < n )

{

i=i^5

i=i/3

i=i∗7

}

What is the complexity of the given program?

Let $V(0)=12$ and $V(j)$ be the value of the variable $i$ immediately after the $j$-th iteration for $j \ge 1$.

$$
\begin{align}
V(j) &= \frac{7}{3} \cdot V(j-1)^5 \\
&= \left(\frac{7}{3}\right)^{1+5} \cdot V(j-2)^{25} \\
&= \left(\frac{7}{3}\right)^{1+5+25} \cdot V(j-3)^{125} \\
&= \dots \\
& = \left(\frac{7}{3}\right)^{\sum_{k=1}^{j-1} 5^k} + V(0)^{5^j} \\
&= \left(\frac{7}{3}\right)^{\frac{5^j - 1}{4}} + 12^{5^j}
\end{align}
$$
(I'm hand-waving a bit when the dots are used. If you want a formal proof you can use induction on $j$).

For your algorithm to stop you need that $V(j) \ge n$. When does this happen?

   Notice that $V(j)$ is monotonically increasing.
 Then, you need more than $s = \lfloor \log_{5} \log_{12} n/2 \rfloor$ iterations since:
 $$V(s) = \left(\frac{7}{3}\right)^{\frac{5^s}{4}} + 12^{5^s} < 2 \cdot 12^{5^s} \le n,$$
 and at most $S = \lceil \log_{5} \log_{12} n \rceil$ iterations since:
 $$ V(S) = \left(\frac{7}{3}\right)^{\frac{5^S}{4}} + 12^{5^S} > 12^{5^S} \ge n. $$

 Each iteration requires constant time (assuming that each arithmetic operation can be carried out in $O(1)$ time, which might or might not be reasonable if you're dealing with large values). Therefore the time complexity is $\Theta(\log \log n)$.


NP-hardness of resource allocation problem I am tring to prove the NP-completeness of the following Binary Integer Linear Program (BILP):

$$ \text{min}\sum_i\sum_j x_{ij}\\
\text{subject to} \sum_jr_{ij}x_{ij} \geq R,\ \ \forall \ \ i \in [L]\\
           \sum_i x_{ij} \leq 1,\ \ \forall \ \ j \in [N]\\
           x_{ij} \in \{0,1\}.$$

This a resource allocation problem in which I am trying to minimize the number of resources utilized while guaranteeing a certain minimum rate for all entities.

$x_{ij}$ is an indicator random variable that indicates whether or not a resource $j$ is allocated to an entity $i$. The first set of constraints impose a minimum amount of resource guaranteed for each entity. $r_{ij}$ is the rate that an entity $i$ can get in a resource element $j$. The second set of constraints ensure that a resource is not allocated to multiple users as sharing of resources is not possible in this problem. $[L]$ is the set of user entities and $[N]$ is the set of resources here.

I have tried looking at several covering problems like set cover that look like this but the second set of constraints
seem to be falling out of place every time. Can anyone suggest an existing NP complete problem that can be reduced
to this problem to prove it's NP-completeness?

Thanks

If you set $N = 2$, and $r_{i0} = r_{i1} = r_i$ for each $i$, and set $R = \frac12 \sum_{i \in [L]} r_i$, then the feasibility of this linear program is precisely the Partition problem. Namely, a feasible solution chooses for each $i \in [L]$ either $x_{i0}$ or $x_{i1}$, so that summing the $r_i$ for those $i$ for which you chose $x_{i0}$ equals $R$, and similarly for $1$.


Hardness of a problem which is the sum of two NP-Hard problems Consider the problem of computing an exponential sum over a certain function $g(x)=f(x)+h(x)$, that is computing
$$\sum_{x}g(x)=\sum_{x}f(x)+\sum_{x}h(x)$$
now if we know that $\sum_{x}f(x)$ and $\sum_{x}h(x)$ are two NP-Hard problems, what can we say about the hardness of $\sum_{x}g(x)$?

Nothing.
Lower bound: Suppose $h(x) = -f(x)$. Then $\sum_x g(x) = 0$, which is trivial to compute. If $\sum_x f(x)$ is NP-hard to compute, then $\sum_x h(x)$ will be too, but $\sum_x g(x)$ will be easy to compute.
Upper bound: Suppose $h(x) = f(x)$. Then $\sum_x g(x) = 2 \sum_x f(x)$, which is as hard as computing $\sum_x f(x)$, which is assumed to be NP-hard. Since NP-hard means (roughly speaking) NP-complete or harder, there is no upper bound on the complexity; it could be arbitrarily hard to compute $\sum_x g(x)$.


Weighted graph clustering with maximum size constraint I'm currently trying to solve a clustering problem. I need to cluster/partition an undirected weighted graph into groups that are restricted to size n.
I have ~80000 nodes and ~260000 edges. Each node owns a weight w. The sum of all node weights in one cluster cannot exceed n. The higher the edge weight between each node, the more "valuable" it is to the cluster. Therefore, nodes with a high weight connection should end up in the same cluster and the loss if a cluster is full should be minimal. The number of clusters created is not pre specified.

I've tried implementing a min cut algorithm (Stoer-Wagner) and execute it over and over again until the size constraint is met. However, the first cut of the graph finished after >30 minutes and created sub-graph consisted of only one node.

Are there any solutions to this problem considering the size constraint? Is there a way to extend a min-cut algorithm to solve this?

Thanks in advance!

I can't think of an exact algorithm and don't know if an efficient one exists. But if you're ok with heuristics and approximate solutions you could try the following:
Find an initial solution:
Repeat the following until every vertex is assigned to a cluster:
Pick a vertex u belonging to no cluster and create a new cluster C = {u0}. Grow a minimum weight tree from {u0} using Prim's algorithm (using only vertices assigned to no cluster) with a cost function corresponding to:
C[v] = minimum over (u=neighbour of v in C) of -value((u,v))/weight(v)

(you just have to adapt the cost update function of any efficient Prim implementation)
Stop when the weight of your Tree starts getting too big.
That's just an idea. You could also try to start with any random assignment of clusters which agrees with the weight constraint.
Perform local optimizations:
Pick a vertex v and see if you can gain value by moving it to another cluster by computing the sum of values of the edges you gain minus the sum of the edges you loose. Pick the cluster which maximizes this sum, among the ones which are possible (i.e, weight(C) + weight(v) <= n). You can repeat that as long as you like or as long as the solution is improving, choosing the vertices in some order or randomly.
If this doesn't work well enough, you can allow to sometimes perform swaps which make your solution momentarily worse in order to get out of a local minimum, using something like Simulated annealing or Tabu Search.


How can an extended linearizable history G be equivalent to sequential history S? I am undertaking a module in Concurrent Programming where some of the new content this year covers linearizability, the Java Memory Model, and sequential consistency. Our class slides are companion slides to The Art Of Multiprocessor Programming.

I have been doing OK with linearizability but have become confused at this point below:

I understand that removing pending invocations gives a complete subhistory, however I cannot understand from this example how a subset G can be equivalent to set S which is larger than it - how is G  obtained from S here?

As far as I am aware there is not enough information to determine if there are pending invocations from the diagram on the right and I am not sure why a --> b is removed in the subset that is G - at first I thought it's because they are overlapping but A and B both have linearization points for viewing them 'as sequential objects'.

I may be over looking something simple and have just misunderstood the slides.

The idea of linearizability is that the parallel events behave as if each of them happened at a single point in time, during the duration of the actual execution of the event. Given a sequence of events, if the end point of event $A$ precedes the starting point of event $B$ then in any linearization, the time point of $A$ must precede the time point of $B$. These are the constraints $\rightarrow_G$, which we can think of as a partial order. The events are linearizable if the constraints are extendable to a linear order $\rightarrow_S$ such that the semantics match — the outcome of the events is the same as if they were applied in the order underlying $\rightarrow_S$. Perhaps this is what was meant by equivalence, though as you mention, it is clearly applied to the wrong objects. What is equivalent here is the actual turn of events and the turn of events given the order $\rightarrow_S$.


Given matrix $A$, find vector $x$ such that every entry of $Ax$ is nonzero Given a matrix $A \in \mathbb{R}^{n \times n}$ with no zero rows, what is the complexity of deterministically finding a vector $x \in \mathbb{R}^n$ such that every entry of $Ax$ is nonzero?

It is easy to see that a vector whose entries are realizations of Gaussian random variables works. Indeed, in this case every entry of $Ax$ is a realization of a continuous Gaussian random variable and, hence, is nonzero with probability $1$. Thus, the probability that all entries of $Ax$ are nonzero is $1$.  Thus if "generate a Gaussian" (or any other continuous random variable) is an allowed operation, then this takes $O(n)$ operations.

In the deterministic case, you probably need at least $O(n^2)$ operations since every entry of the matrix $A$ probably needs to be read. I'm wondering if you could do it in $O(n^2)$ or, if not, what the best time that you can do this in is.

Edit: I don't seem to have enough reputation to post comments on my own question. In any case, let us suppose that the entries of $A$ are all rational, and we are looking for a vector $x$ with rational entries.

Define
$$
M = 1 + \frac{\max_{ij} |A_{ij}|}{\min'_{ij} |A_{ij}|},
$$
where the minimum is taken over all non-zero entries. Then the vector $x$ given by $x_j = M^{j-1}$ satisfies your condition.

Indeed, consider some row $A_{i\cdot}$, and suppose that $A_{ik} \neq 0$ but $A_{i\ell} = 0$ for all $\ell > k$. Suppose, without loss of generality, that $A_{ik} > 0$ and that $\min'_{ij} |A_{ij}| = 1$. Then
$$
(Ax)_i = \sum_{j=1}^k A_{ij} M^{j-1} \geq M^{k-1} - (M-1) \sum_{j=1}^{k-1} M^{j-1} = 1.
$$

Whether the encoding of $x$ is small enough depends on your exact computation model.


Why the language of unary primes isn't regular I have some difficulties proving that the language of unary primes ($L=\{1^p\mid p\text{ is prime}\}$) is not regular using the pumping lemma. Any suggestions?

This is one of the more difficult common applications of the pumping lemma, so I'll give you an outline to get you started.

Suppose $L$ is regular and let $k$ be the pumping length.  Let $p$ be a big enough prime* so $1^p\in L$, and write $a=1^r1^s1^t$, with $r+s\leq k$ and $s\geq 1$, so $t=p-r-s$.  You need to find some $n$ such that $1^r(1^s)^n1^t\notin L$, i.e., such that $r+ns+t$ is not prime, which you can show by writing it as a product of two factors, both strictly bigger than $1$.

* You'll certainly need $p>k$ to apply the pumping lemma, but you might need it to be bigger still, to guarantee that the factors are bigger than $1$.


Associativity vs blocks per set in fixed size caches I am trying to understand the following claim:

  For a fixed size cache, each increase by a factor of two
  in associativity doubles the number of blocks per set
  (i.e., the number or ways) and halves the number of
  sets – decreases the size of the index by 1 bit and
  increases the size of the tag by 1 bit.

I am just wondering if someone can clear this up for me. For example, if there is a cache with 16 cachelines and it's 2-associative the number of blocks per set is 8, but if we increase by a factor of two associativity then the number of blocks per set decreases to 4.

The number of sets determines the size of the index, because the index tells you what set to refer to.  If you increase associativity by giving more blocks to each set then you run out of blocks sooner and so you can afford fewer sets.  If you have fewer sets then you have a smaller index.

If half the sets disappear then those addresses have to be handled by the remaining sets.  Because each set now has more addresses that it serves, it needs an extra bit of tag to distinguish them.


Ambiguity Problem (Language Structures) I'm having serious issues fining an unambiguous version of a particular grammar. I've looked online for help for this particular problem and for general methods for finding unambiguous versions of grammars, and though I understand the concept, I can't seem to figure this out. Any help/advice? I keep getting really close then finding something that doesn't fit. Here is the grammar in question:

S -> aS | bS | Sa | Sb | aa

The language of the grammar $G$ presented here is regular and its corresponding regular expression is
$$r = (a \mid b)^*aa(a \mid b)^*.$$
Now, convert the regular expression to a minimal finite automaton and use this question to convert the automaton to an unambiguous regular grammar, which is always possible.
In the end you can get something like this:

$$
\begin{align}
S &\rightarrow aA \mid bS \\
A &\rightarrow aB \mid bS \mid a \\
B &\rightarrow aB \mid bB \mid \epsilon
\end{align}
$$

Proof that $\mathscr{L}(r) = \mathscr{L}(G)$: (1) Let $s \in \mathscr{L}(r)$, hence $s = x aa y$, where strings $x,y$ consist of characters $x_i, y_j \in \Sigma, i = [1..m], j = [1..n], m = |x|, n = |y|$.
There is a derivation of $s$:
$$S \rightarrow x_1S \rightarrow x_1x_2S \rightarrow ... \rightarrow x_1...x_mS = xS \rightarrow xSy_n \rightarrow xSy_{n-1}y_n\rightarrow ... \rightarrow xSy_1...y_n = xSy \rightarrow xaay.$$
Thus $s = xaay \in \mathscr{L}(G)$ and $\mathscr{L}(r) \subseteq \mathscr{L}(G)$.

(2) Let $s \in \mathscr{L}(G)$. This means there exists some derivation
$$S \rightarrow \alpha_1 \rightarrow \alpha_2 \rightarrow ... \rightarrow \alpha_p = s.$$
Observe that the only way to make the non-terminal $S$ disappear is to use the rule $S \rightarrow aa$ and it must be the last step of the derivation:
$$S \rightarrow \alpha_1 \rightarrow ... \rightarrow \alpha_{p-1} = xSy \rightarrow \alpha_p = s = xaay,$$
where $x,y$ are some strings of terminals.
Thus $s = xaay \in \mathscr{L}(r)$ and $\mathscr{L}(G) \subseteq \mathscr{L}(r)$, resulting in $\mathscr{L}(G) = \mathscr{L}(r)$. Qed.


Language theoretic comparison of LL and LR grammars People often say that LR(k) parsers are more powerful than LL(k) parsers. These statements are vague most of the time; in particular, should we compare the classes for a fixed $k$ or the union over all $k$? So how is the situation really? In particular, I am interested in how LL(*) fits in.

As far as I know, the respective sets of grammars LL and LR parsers accept are orthogonal, so let us talk about the languages generated by the respective sets of grammars. Let $LR(k)$ denote the class of languages generated by grammars that can be parsed by an $LR(k)$ parser, and similar for other classes.

I am interested in the following relations:

$LL(k) \overset{?}{\subseteq} LR(k)$
$\bigcup_{i=1}^{\infty} LL(k) \overset{?}{\subseteq} \bigcup_{i=1}^{\infty} LR(k)$
$\bigcup_{i=1}^{\infty} LL(k) \overset{?}{=} LL(*)$
$LL(*) \overset{?}{\circ} \bigcup_{i=1}^{\infty} LR(k)$

Some of these are probably easy; my goal is to collect a "complete" comparison. References are appreciated.

There are numerous containments known. Let $\subseteq$ denote containment and $\subset$ proper containment. Let $\times$ denote incomparability.
Let $LL = \bigcup_k LL(k)$, $LR = \bigcup_k LR(k)$.
Grammar level
For LL

$LL(0) \subset LL(1) \subset LL(2) \subset LL(2) \subset \cdots \subset LL(k) \subset \cdots \subset LL \subset LL(*)$
$SLL(1) = LL(1), SLL(k) \subset LL(k), SLL(k+1) \times LL(k)$

Most of these are proven in Properties of deterministic top down grammars by Rosenkrantz and Stearns. $SLL(k+1) \times LL(k)$ is a rather trivial exercise. This presentation by Terence Parr places $LL(*)$ on slide 13. The paper LL-regular grammars by Jarzabek and Krawczyk show $LL \subset LLR$, and their proof trivially extends to $LL \subset LL(*)$
For LR

$LR(0) \subset SLR(1) \subset LALR(1) \subset LR(1)$
$SLR(k) \subset LALR(k) \subset LR(k)$
$SLR(1) \subset SLR(2) \subset \cdots \subset SLR(k)$
$LALR(1) \subset LALR(2) \subset \cdots \subset LALR(k)$
$LR(0) \subset LR(1) \subset LR(2) \subset \cdots \subset LR(k) \subset \cdots \subset LR$

These are all simple exercises.
LL versus LR

$LL(k) \subset LR(k)$ (Properties of deterministic top down grammars plus any left recursive grammar)
$LL(k) \times SLR(k), LALR(k), LR(k-1)$ (simple exercise)
$LL \subset LR$ (any left recursive grammar)
$LL(*) \times LR$ (left recursion versus arbitrary lookahead)

Language level
For LL

$LL(0) \subset LL(1) \subset LL(2) \subset \cdots \subset LL(k) \subset \cdots \subset LL \subset LL(*)$
$SLL(k) = LL(k)$

Most of these are proven in Properties of deterministic top down grammars. The equivalence problem for LL- and LR-regular grammars by Nijholt makes references to papers showing $LL(k) \subset LL(*)$. The paper LL-regular grammars by Jarzabek and Krawczyk show $LL \subset LLR$, and their proof trivially extends to $LL \subset LL(*)$
For LR

$LR(0) \subset SLR(1) = LALR(1) = LR(1) = SLR(k) = LALR(k) = LR(k) = LR$

Some of these were proven by Knuth in his paper On the Translation of Languages from Left to Right in which he introduced LR(k), the rest are proven in Transforming LR(k) Grammars to LR(1), SLR(1), and (1,1) Bounded Right-Context Grammars by Mickunas et al.
LL versus LR

$LL \subset LR(1)$ (containment follows from the above, $\{ a^i b^j | i \geq j \}$ is the canonical example for strict containment)
$LL(*) \times LR$ (the language $\{ a^i b^j | i \geq j \}$ shows half the claim, and the introduction of The equivalence problem for LL- and LR-regular grammars by Nijholt makes references to papers showing the other half)
$LR(1) = DCFL$ (see e.g. reference here).


Perform the following 8-bit two's complement arithmetic operation How am I supposed to perform this subtraction?

For instance: $01110000_2−11101011_2$

$01110000_2$ has a positive sign, so there is no need to perform two's complement. $11101011_2$ has a negative sign, so I need to perform two's complement.

Two's complement for $11101011_2$ is $00010101_2$

Finally, I must perform the subtraction $01110000_2 - 00010101_2 = 1011011_2$

Two's complement is a way of representing positive and negative numbers in binary.  There is a very good explanation here: https://stackoverflow.com/questions/1049722/what-is-2s-complement

Basically, the really clever part about two's complement is that arithmetic works without making any special changes.  Let's look at that in action with n addition operation: $10000001 + 00010000 = 10010001$.  Notice that no special actions were taken in finding the sum.  Nevertheless, what I've written there is that $-127 + 16 = -111$.

Two's complement is really just a clever way of encoding the numbers designed to make arithmetic straightforward.

By the way, an easy way of reading two's complement numbers is just to reverse the sign on the highest bit.  To illustrate what I mean by this, regularly encoded (non-complement) 8-bit integers like $10010011$ and $01000010$ could be found by adding $1 + 2 + 16 + 128 = 147$, and $2 + 64 = 66$ respectively.

If we were to designate these same numbers as two's-complement, we would just reverse the sign on the 128s bit.  Now our two numbers would be  $1 + 2 + 16 -128 = -109$, and $2 + 64 = 66$.  The second number didn't change because the highest bit was a $0$ already, so it doesn't matter if we are adding or subtracting it.

So, if you were to try to subtract $01110000−11101011$, let's get an answer first so that we can check ourselves.  $64+32+16 = 112$, and $-128+64+32+8+2+1 = -21$.  You are performing the subtraction $112 - -21$.  This means that our final answer should be $133$.

So, just as you can subtract by negating before you add (ie. $112 + 21$ instead of $112 - -21$), we can perform a similar operation here.  If we negate the second number, we flip the bits and add one: $00010100 + 1 = 00010101$.  But now that we've negated the number, our subtraction has become an addition problem.  So, our original $01110000−11101011$ has become $01110000 + 00010101$

  01110000
+ 00010101
  --------
  10000101

$10000101$ is $-128 + 4 + 1$, which equals...

$-123$.

-123?? Wait, what happened?

We've fallen into the classic two's complement trap!  Because we only have 8 bits, we only have a limited range of possible numbers.  8 bits allows for 256 possible values.  Two's complement divides these values nicely: half are positive and half are negative, giving us a range of $-128$ to $127$.  Why one less in the positives?  It's because Zero has to be somewhere, and since $00000000$ doesn't start with a leading $1$, it comes out of the positive space.

If you're just doing pure math, simply add an extra digit, and you'll be out of trouble.  $010000101$ is $128 + 4 + 1$, which equals $133$. If you're on a computer, however, you have to pay more attention to this problem.

When you go outside of the range of your bits, you are said to have an overflow error.  Modern processors and languages have evolved ways of dealing with this problem, typically through flagging operations that might have caused overflow.


Type-checking algorithms I am starting a personal bibliographic research on type-checking algorithms and want some tips. What are the most commonly used type-checking algorithms, strategies and general techniques?

I am particularly interested in complex type-checking algorithms that were implemented in widely known strongly static typed languages such as, for example, C++, Java 5+, Scala or others. I.E, type-checking algorithms that are not very simple due to the very simple typing of the underlying language (like Java 1.4 and below).

I am not per se interested in a specific language X, Y or Z. I am interested in type-checking algorithms regardless of the language that they target. If you provide a answer like "language L that you never heard about which is strongly typed and the typing is complex has a type-checking algorithm that does A, B and C by checking X and Y using the algorithm Z", or "the strategy X and Y used for Scala and a variant Z of A used for C# are cool because of the R, S and T features that works in that way", then the answers are nice.

Most research does not actually publish the type checking algorithms for full blown programming languages. You will find some formalisations of a large part of the type systems for full programming languages, such as the work done by Drossopoulou and Eisenbach for Java or Nipkov et al's work on C++. More often, though, you will only find the type systems for some core part of the language (Featherweight Java is one example) or for the core concepts of a language such as the local type inference approach of scala.

In conferences such as POPL and ICFP you will find many type checking algorithms for specific kinds of type systems, and novel approaches such as bidirectional and tridirectional type checking.

More generally, you probably need to know about the Damas-Milner algorithm, local type inference, bidirectional and tridirectional type checking, and expand from there, by following references in the papers and by using google scholar to find which papers cite these and build on the approaches described. Also, as suggested above, conferences such as POPL, ICPF, ESOP and even ECOOP and OOPSLA will have papers relevant to your quest.


One element that differs in two arrays. How to find it efficiently? I am preparing for a coding interview and I can't really figure out the most efficient way to solve this problem.

Let's say we have two arrays consisting of numbers that are unsorted. Array 2 contains a number that Array 1 does not. Both arrays have randomly located numbers, not necessarily in the same order or at the same indices. For example:

Array 1
[78,11, 143, 84, 77, 1, 26, 35 .... n]

Array 2
[11,84, 35, 25, 77, 78, 26, 143 ... 21... n+1]

What is the fastest algorithm for finding the number that differs? What is its running time? In this example, the number we would be looking for is 21.

My idea was to run through Array 1 and delete that value from array 2. Iterate until you are finished. This should be around $O(n \log n)$ running time, right?

I see four main ways to solve this problem, with different running times:

$O(n^2)$ solution: this would be the solution that you propose. Note that, since the arrays are unsorted, deletion takes linear time. You carry out $n$ deletions; therefore, this algorithm takes quadratic time.
$O(n \: log \: n)$ solution: sort the arrays beforehand; then, perform a linear search to identify the distinct element. In this solution, the running time is dominated by the sorting operation, hence the $O(n \: log \: n)$ upper bound.

When you identify a solution to a problem, you should always ask yourself: can I do better? In this case, you can, making a clever use of data structures. Note that all you need to do is to iterate one array and perform repeated lookups in the other array. What data structure allows you to do lookups in (expected) constant time? You guessed right: a hash table.

$O(n)$ solution (expected): iterate the first array and store the elements in a hash table; then, perform a linear scan in the second array, looking up each element in the hash table. Return the element that is not found in the hash table. This linear-time solution works for any type of element that you can pass to a hash function (e.g., it would work similarly for arrays of strings).

If you want upper-bound guarantees and the arrays are strictly composed of integers, the best solution is, probably, the one suggested by Tobi Alafin (even though this solution will not give you the index of the element that differs in the second array):

$O(n)$ solution (guaranteed): sum up the elements of the first array. Then, sum up the elements of the second array. Finally, perform the substraction. Note that this solution can actually be generalized to any data type whose values can be represented as fixed-length bit strings, thanks to the bitwise XOR operator. This is thoroughly explained in Ilmari Karonen's answer.

Finally, another possibility (under the same assumption of integer arrays) would be to use a linear-time sorting algortihm such as counting sort. This would reduce the running time of the sorting-based solution from $O(n \: log \: n)$ to $O(n)$.


Anotation rules for while rule in deductive verification I have been studying deductive verification of software lately, with weakest precondition, strongest postcondition, annotation calculus, and etc.
I came across the following rules for the while sentence:

But, my problem is when should I use which rule? I mean the second and third one that includes $t$, which is the variant here, is usually related to the loop condition, but when again when should I use the second while and when the third one? I couldn't find any clarification anywhere about when to choose which one.  (Note that $t$ is not a variable of the program, but a variant used to prove termination.)

As you have already said, the second and third rule include a variant t to prove termination whereas the first rule does not consider it.

The second rule guarantees that the variant is always non-negative. This is necessary to have a lower bound for the variant which decreases every iteration.

The third rule relaxes that condition a little bit. The variant is always non-negative except in the last iteration (where e is false at the end of the block). This still guarantees termination (who cares about the variant if we know it's the last iteration?).

I think whether you choose the second or third rule is a matter of taste. Until now I knew only the second one. It should be easy to alter code or a variant whose correctness can be shown by the third rule such that it is also provable with the second one.

Choosing the first rule is of course only an option if you're not interested in termination.


2-SAT implication Understanding Having a simple 2-SAT problem where the equation is simply: $a \lor b$

We have two implications:

$\lnot a \Rightarrow b$
$\lnot b \Rightarrow a$

Thus, in the graph we build we add edges similar to the arrows above.

What exactly do the arrows symbolise in this instance? I've read that they means if $a$ is true, $b$ must be true as well. The same for false. Why can we model this equation in such a way?

You are asking why we can model the equation $a \lor b$ as two directed edges in a graph. The answer is that mathematics is a free country, and we are allowed to do whatever we want. The only restriction we have to obey is that whenever we claim a result, it must be accompanied by a valid proof.

This representation is used in an algorithm that decides whether a 2SAT instance is satisfiable. As you mention, an edge from a literal $\ell_1$ to a literal $\ell_2$ means that if $\ell_1$ is true, then $\ell_2$ has to be true. Indeed, if $a \lor b$ holds then if $\lnot a$ is true, $b$ must be true, and vice verse, if $\lnot b$ is true, $a$ must be true.

If there is a path from some literal to its negation – from $x$ to $\lnot x$ or from $\lnot x$ to $x$, for some variable $x$ – then clearly the formula is not satisfiable, since $x$ cannot be both true and false. A more delicate argument shows that if no such paths exist, then the formula is satisfiable. This is proved by showing how to find a satisfying assignment for the formula (it's a nice exercise).


weak Church-Turing thesis (weak) Church-Turing thesis states every physically realizable computation device can be simulated by a Turing machine (not necessarily efficiently).
(1) Then Does any model that is not physically realizable and cannot be simulated by Turing machine?
(2) Is there any evidence for this thesis?

You are asking two questions. The answer to your first question, for models stronger than Turing computation, is the field of hypercomputation. The answer to your second question, asking for evidence for the Church-Turing thesis, has been answered on cstheory.


Do Kernel-Mode Windows Services Considered Part of Kernel? I learned that there are two types of services in Windows , one called -service- which is in user-mode , other is called -driver service / device driver- which is in kernel-mode.

What I wonder is , do kernel-level services considered as a part of the kernel? If so , does writing kernel-mode services mean extending Operating System?

My lecturer accepts the definition of OS as , it is solely the Kernel. So I wonder if kernel-level services are included in his OS definition.

Are kernel-level services considered as a part of the kernel?

That can be debated, but for me the answer is yes.

You might run into a purist who considers only the code from the manufacturer in the kernel to be part of the kernel and extensions as an add on the kernel. I would ask you instructor for his answer, you are the customer, right?

  If so , does writing kernel-mode services mean extending Operating System?

For me it surely does.

The easiest way to think of this is adding a device that requires installing a kernel mode device driver. Once the kernel mode device driver is installed all the code has access to the device driver in the same way all the code has access to the kernel. That is simplified but you should get the analogy.


How does mathematical software evaluate symbolic sums? Wolfram alpha is able to compute this sum:
$$ \sum_{j=1}^n \binom{j}{2} = \frac{1}{6}(n-1)n(n+1). $$

How can Wolfram alpha do it? What kind of algorithm does it use?

It uses algorithms discussed in the book A=B by Petkovšek, Wilf and Zeilberger. These algorithms can compute a closed-form expression for a summation of rational functions (in your case, the rational function is $j(j-1)/2$), or determine that no such closed-form expression exists.


(Non) Context Free language? In an exam question it is asked to identify if the given language is Context-Free, Non Context Free or Regular.
This is the question :

In my opinion this language is not a CFL since w doesn't belong to L', meaning that it belongs to not(L') which is all words (a^n b^n c^n) which is not CFL.

Apparently my answer is not right and I really don't understand why... Is this question a "trap" because i,j,k > 0 and not >= ? Meaning that a word (b^n c^n) is in L ? Looks like I'm lost !

I really need your help and explantions.

Thanks in advance.

It helps to think of $L$ as having two parts.

First part: $L_1$ is all strings not in the form $a^i b^j c^k$. We can write this with the regular expression $\neg [a^* b^* c^*]$, so it's regular.

(I've been informed this notation isn't universal, so to spell it out: it's the complement of the regular language $a^* b^* c^*$, and the complement of a regular language is regular.)

Second part: $L_2$ is all strings in the form $a^i b^j c^k$ such that the given conditions on $i, j, k$ are not fulfilled.

The given conditions are that $i, j, k$ are all different. So how can those conditions be violated? Either $i=j$, or $j=k$, or $i=k$. We can call these three options $L_{2a}$, $L_{2b}$, and $L_{2c}$ if you want.

Let's take just one of them as an example; the others work the same way. $L_{2a}$ is all strings of the form $a^i b^i c^k$. Can you write a regular expression for this? How about a CFG? (The answers are no, and yes: in fact, this is one of the classic examples for what a CFG can do that a regular expression can't.)

Now, since $L_{2a}$, $L_{2b}$, and $L_{2c}$ are all context-free, their union ($L_2$) is also context-free. And since $L_1$ is regular, it's also context-free. So $L$, as the union of two context-free languages, is context-free.


Algorithm to check whether a complete, undirected graph is fullfilling the triangle inequality I am searching for an algorithm to check whether a complete, undirected graph is fullfilling the triangle inequality( $\text{weight}(u,v) \le \text{weight}(u,w) + \text{weight}(w,v)$ for all vertices $u, v, w$).

My first naive try was to use an algorithm for solving the all-pairs-shortest-path-problem and compare the result to the vertices connecting two nodes directly.

However, I think this might be overkill. Is there any better way to check?

Thanks a lot.

Yes.  If you have a complete graph, the simplest algorithm is to enumerate all triangles and check whether each one satisfies the inequality.  In practice, this will also likely be the best solution unless your graphs are very large and you need the absolute best possible performance.  For instance, enumeration will likely be faster than most shortest-paths algorithms.

None of the shortest-path algorithms provide better asymptotic runtime; they are more complicated to implement; and they will be slower in practice (because of a larger constant factor).

As AJed correctly points out, you can use matrix multiplication to beat the $O(n^3)$ bound.  However, this requires a bit more care.  While there are algorithms for matrix multiplication that are faster than $O(n^3)$ time, the algorithms are tricky to implement, so if you take this approach, you might want to use an existing library/implementation (e.g., BLAS).  Also, the asymptotically optimal algorithms (e.g., Coppersmith/Winograd, Stothers, Williams) only become faster once $n$ becomes extremely large so they won't be worthwhile in practice.  This suggests that if you want to wring out every last bit of performance, you'll need to actually benchmark this on realistic workloads: asymptotic complexity can be misleading.

If you care about extreme optimization, cache effects may also play a huge role here, so the way the graph is laid out in memory may have a significant effect on the constant factors.  Fortunately, if your graph is represented as an adjacency matrix, standard libraries for matrix multiplication already take this into account.

If it were me, I'd just enumerate all triangles and check the triangle inequality.  If you run into a problem domain where this is the bottleneck in the overall computation and where it is too slow, then you could consider more sophisticated approaches, like using matrix multiplication, at that point.  To paraphrase Knuth, "Premature optimization is the root of all evil".


Hashing methods for validating dowloaded files The standard algorithm to generate hashes of files which are downloaded is MD5. For example, when ISO files of Linux distributions are offered most of the time they also give the MD5 sum so that you can check if an error happened while downloading the file.

I'm aware of the fact that MD5 should not be used for password hashing as it is fast to compute. However, in the case of downloaded files I think it is desirable if it is computed fast.

Hence my question: Which hashing algorithm is recommended? What are the relevant criteria? If it is easy to find collisions of a hashing algorithm, does that automatically imply that it should not be used in scenarios where one does not expect attacks, but only "random" errors?

There are several reasons why one might want to add some extra material to validate a downloaded file. Different reasons require different kinds of extra material.

Non-malicious corruption

A common type of corruption is that files get truncated. For this, the size is enough.

To detect accidental corruption of the downloaded file for hardware reasons (bits getting flipped, lost or reorderd in transit), any kind of checksum helps. It doesn't have to involve cryptography — for this purpose, MD5 is a little overkill, but suitable. Against accidental corruption, a well-designed checksum that can take $n$ different values has a probability of $1-\frac{1}{n}$ of detecting the corruption.

Malicious corruption, single-file scenario

Malicious corruption is another matter. Against malicious corruption, you need two things:

A known secure channel. Without something to bootstrap security, the recipient has no way to know that what they're getting isn't wholly coming from an adversary.
A cryptographic tie between the secure channel and the download channel.

The reason to have two separate channels is, to put it succinctly, bandwidth. The goal is to insert the downloaded file into a chain of trust that starts from a computer and its operating system, and may rely on additional assumptions, e.g. trust in a particular website.

An example of a channel separation is when you trust some website (hopefully served over HTTPS, but you don't trust the channel through which the file is downloaded. In practice, these days, often the file would be distributed on the same website, and a separate verification doesn't provide any additional security. However separate verification can still be useful, for example if you've already downloaded the file in the past, but you aren't sure whether your local copy is pristine or whether it's the right version.

To establish a cryptographic tie, the basic method is to use a cryptographic hash function: calculate the hash of the large file distributed through the insecure channel, and distribute the hash through the secure channel. One of the properties of a cryptographic hash $H$ is that it's infeasible to find $x' \neq x$ such that $H(x') = H(x)$ (second preimage resistance); here this means that it's impossible to generate a fake file that has the genuine hash.

MD5 was designed to be a cryptographic hash function, but it is now known not to be one. Its second preimage resistance is not broken yet, but due to the weaknesses that have been found in MD5, the cryptography community no longer trusts it for anything. What has been broken for MD5 is its collision resistance, i.e. there are cheap ways of generating $x \ne x'$ such that $\mathrm{MD5}(x) = \mathrm{MD5}(x')$. (Note the difference with second preimage resistance: here the adversary does not get to choose the hash value.)

In addition to the risk that an attack would be found on second preimage resistance, there's a reason not to use MD5 to verify that something is genuine. Because collisions can be generated, it's possible to perform a bait-and-switch attack:

Generate a file with “good” contents (e.g. well-behaved software), and another file with “bad” contents (e.g. malware).
Have people review the good file and give it a good reputation.
Distribute the bad file.

This attack can be performed without the distributor being aware, if they're redistributing third-party content (e.g. a picture whose bad version triggers an exploit in an image viewer).

The state of the art of cryptographic hash functions is the SHA-2 family (generally SHA-256 or SHA-512). (There are a few alternatives but they don't get used much in the real world as of 2017.) Cryptographic hash functions are designed for speed, and there is no meaningful difference between MD5 and SHA-256 in practice in most scenarios — I/O is usually the limiting factor, not computation.

Password hashes are a different kind of function (closely related to key stretching) which are used in a specific case: when the data to be hashed has to be secret and cannot be encrypted (in the case of a password, the objective is to make the password hard to guess even if the adversary obtains all the information that the legitimate verifier has, including any encryption keys). Password hashes need to be slow to limit the impact of brute force guess attempts. Hashes used in other scenarios don't need this and are designed for speed.

A cryptographic hash function is a way to expand integrity. Assuming the integrity of the channel through which you obtain the hash, you get a guarantee of integrity of the hashed data.

A hash does not guarantee authenticity: it doesn't say who made this file. Anybody can calculate the hash of a file. To know that the file is authentic, you need to trust the authenticity of the channel through which you receive the hash.

Malicious corruption: many-files scenario

There is another useful cryptographic primitive that is useful to distribute files: signatures. Where a hash propagates integrity, a signature propagates authenticity. Suppose you have a public key distributed through a secure channel (as in, a channel that guarantees the authenticity of the data, i.e. you know who the public key came from, and that it wasn't corrupted in transit). Then you can retrieve a signed file distributed through an insecure channel, and verify whether it has a correct signature. Whereas anybody can calculate the hash of a file, generating a valid signature requires the knowledge of the private key that is associated of a public key.

A signature allows distributing a single datum through the secure channel (the public key) and many large files through the insecure channel. In particular, if the distributor wants to distribute a new file, they can sign it and they don't have to update anything through the secure channel. So the secure channel can be offline, e.g. an operating system image.

The next level after signatures is signatures of signatures. For a file distribution mechanism, signatures introduce a bottleneck: the holder of the private key has to sign all the files. A mechanism where one entity signs other entities' public keys is called a public key infrastructure.

Note that signatures ensure that correctly-signed data is genuine, but they do not assure freshness — they do not protect against attacks such as replay attacks. The correctness of a signature is a mathematical property and does not decay in time. An attacker could, for example, hide a security update by continuing to distribute the old, vulnerable version of some software, even after a fix has been published. Protecting against such attacks requires verifying the freshness of a file via a secure channel (here, the security properties required from the channel are freshness and authenticity). This doesn't have to involve cryptography (beyond any cryptography that might be involved in the secure channel), it can be a simple check of a version number or publication date.


Building segment tree without adding extra elements to its size I recently learned about segment trees as data structures, and what I learned was that we are always building segment tree with size $N$ such that $N$ is power of two. If $N$ is not power of two we can add more elements to the end of the tree.

However, I was wondering is the segment tree going to work normally if we don't add more elements to make its size power of two.

Example

If the size of segment tree is 8, then we have array of size 15, $15 = 2 \cdot 8-1$
In this array we keep track of the intervals, where we have the interval $[1,8]$ on index 1, and on index $2\cdot 1$ we keep the left child, and the right child is on index $2\cdot1+1$.

So our array looks like following:

index $1: [1, 8], 2: [1, 4], 3: [5, 8], 4: [1,2], 5:[3, 4],6:[5, 6], 7:[7, 8]$,  $8[1, 1], 9:[2, 2], 10:[3,3], 11:[4,4], 12:[5,5], 13:[6,6], 14:[7, 7], 15:[8,8]$

Now my question is this: If we run this algorithm for dividing and building the segment tree for numbers that are not power of two (ex. 7, 11, 15).. is it going to build the segment tree normaly, because the segment tree  is not going to be full balanced then.

A segment tree is not required to be full (which is what I believe you mean), however it will always be complete. That is, every level, except possibly the last, is filled.

Take a look at the structure and construction to see that it says nowhere that was must have $2^k - 1$ nodes in the tree. For example we may have $2^{k-1} < c < 2^{k}$ elementary intervals, making our tree non-full, but absolutely complete.

Example, let's say we have intervals:

$$I = \{[1, 5]^A, [2, 3]^B, [2, 8]^C, [4, 6]^D, [4, 10]^E, [5, 9]^F, [7, 8]^G\}$$

We then have the endpoints of the elementary intervals:

$$I' = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$$

Now we construct a balanced tree with just the end points as leaves:

Next when we insert intervals to get:

This is fine. Adding in the extra elements is usually a convenience. This is mostly a convenience when using an array to implement the tree. For efficiency reasons, using an array is almost always preferable to an actual tree (Node) object because there is much less overhead. Arrays also make it easier/more natural to implement searching/insertion iteratively rather than recursively which decreases another factor of overhead. The sacrifice of adding at most $2x$ as many nodes is generally worth it. Asymptotically there is no difference.

Okay, so using an array is preferable, but why do we need $2^k - 1$ elements? If we have a full binary tree there is almost no edge case handling. Imagine in a recursive procedure we produced a tree like the one above. What would it look like in an array?

I'll show the two different proposals.

Our tree if we filled up the last layer and moved all elementary boundaries to leaves (leaves in red and the gradient shows least to greatest boundary, levels are different colored blue boundaries)

Our tree if we do not fill up the last layer and left leaves as is.

Clearly (1) should look more appealing, but it is also functionally more appealing. There is only one leaf level, so we need no conditional checking if we are at a leaf or not, we just check which iteration into the tree we are at. There are simply more checks to do per iteration and it is not worth it over filling in the final level. So you can do it, but I wouldn't.


How to express the existence of winning strategy of the starter of a game in temporal logic? Consider a two-player game. A winning strategy of a player is a strategy following which the player can always beat his opponent, no matter how his opponent responds.

A game can be unfolded to a state space consisting of the possible ways of both sides of the game. How to express the existence of winning strategy of the starter of a game, say player 1, in temporal logic, defined on such a state space? The temporal logic formula can be used for model checking.

Using CTL, I get $\exists \Box (\exists \Diamond \textsf{Win}_1)$, meaning that there exists a path (from the initial state) such that from each state of this path there exists a path that eventually leads to a winning state for player 1. Is this correct?

Can it be expressed in LTL or any other variants of temporal logic?

I don't think it's possible in CTL nor LTL to model two competing players.

You would probably need ATL (Alternating-time Temporal Logic).  In ATL, the formula $\langle\langle A \rangle\rangle \phi$ says that agent (or coalition) $A$ can enforce $\phi$ to come about.  In your case, $\langle\langle P_1 \rangle\rangle \text{Win}_1$.

In modal µ-calculus, it should definitely be doable.  Something like $\mu Z . \big( \text{Win}_1 \lor \Diamond \Box Z \big)$?


Is there any precedence for symbols for constructing parse trees? I am wondering if some symbols such as the ones in propositional logic have precedence over others in drawing parse trees.

For example, the sentence: p ∧ q → r, would ∧ take precedence over → in becoming the root of the parse tree or vice versa?

Or is there no precedence meaning, → or ∧ could be used the root?

Operator precendences have to be specified, either in the grammar or using other means. There is no inherent precendence to rules, but you can fix one arbitrarily.


Optimal substructure and dynamic programming for a variant of the rod cutting problem The rod-cutting problem described in Section 15.1 of CLRS, 3rd edition is the following.

  Given a rod of length $n$ inches and a table of prices $p_i$ for $i = 1, 2, \ldots, n$, determine the maximum revenue $r_n$ obtainable by cutting up the rod and selling the pieces.

This can be solved by dynamic programming with the recursion (consider the leftmost piece of length $j$):
$$R(i) = \max_{1 \le j \le i} \Big(p_j + R(i-j)\Big),\; R(0) = 0,$$
where $R(i)$ denotes the maximum revenue obtainable by cutting up a rod of length $i$.

In exercise $15.3$-$5$, a variant is considered:

  we also have limit $l_i$ on the number of pieces of length $i$ that we are allowed to produce, for $i = 1, 2, \ldots, n$.

Problem: Is this variant of the rod cutting problem solvable using dynamic programming?

Answer My Own Question:

Let $L$ be the length limit array.

Define $R(i, L)$ to be the maximum revenue obtainable by cutting up a rod of length $i$ with the length limit array $L$. The recursion is (consider the leftmost piece of length $j$; the base cases are not included):

$$R(i, L) = \max_{1 \le j \le i \land L_j \ge 1} \Big(p_j + R\big(i-j, L[j \mapsto L_j-1]\big)\Big),$$
where $L[j \mapsto L_j - 1]$ leaves other length limit than $L_j$ unchanged.


Prime checking and factorization with just bit cheking I've read about some methods of prime factorization like here and here. However, I'm wondering: what can we do in prime factorization with just some bit manipulation and without other variables/constants?

In base 10, we can get some hints about the factors of an integer just be checking the digits:

digit's place is even --> int is even
digit's place is 0 of 5 --> int is divisible by 5
sum_of_digit % 3 = int % 3
sum_of_digit % 9 = int % 9

Given an integer num as a bit array, how can we check for num's primality and guess or extract its prime factors just by looking at its bits like we do with digits in base 10?

   There are 5 0's --> (num % (2^5)) = 0
            / \
           /   \
           |   |
1010101110100000
      | |      ^
      | |      | last bit is 0 --> num is even
      | |
       v
may be these 3 bits can give some information?

What's allowed:

bit-manipulations which take 1 argument are allow. This includes functions like not but not xor.
ifs and loops are allowed but bits in num will be used for the flag. (no using if num > 2)
num is the only variable/constant allowed to be declared. We can not(num) (flip every bits in num) but not num - 2 (2 is another var/const).
Operating on bits only in num like summing all the bits (bit_sum(20) = bit_sum(b1010) = 2 because there are 2 1s)

Bonus if the operation can quickly be done by hand like the given examples for base 10.

Given any specific candidate divisor $d$, it is easy to check whether $d$ is a divisor of the number (the standard modular reduction algorithm is a generalization of those tricks you mentioned).  This can be done for all $d$.  However, it doesn't help with efficient factorization, because there are exponentially many candidate divisors, so trying each one, one-by-one, is far too inefficient.

In other words, this approach to factorization is not likely to be useful, no matter how many tricks you accumulate.


How to use an algorithm to find a satisfying assignment in polynomial time? I am currently trying to solve the following problem but I am unsure how to go about it. The problem states:

Suppose that someone gives you a polynomial-time algorithm to decide 3-SAT. Describe how to use this algorithm to find a satisfying assignment in polynomial time.

To my understanding the 3-SAT is simply a conjunction of any 3 disjunctions that turns out to be true (i.e. something like (x1 | x2 | x3) & (x4 | x5| x6) where | represent or and & represents and). In this case you could have used any ordering of the variables and you could have negated them at your pleasure. Furthermore You can keep adding conjunctions, but each one has to have 3 variables. Please correct me if I am wrong in any statement above.

Now, they want us to find a satisfying assignment in polynomial time, meaning values of x1, x2, x3, x4, x5, x6 that make the value true. However, isn't that what we are given in the first place? I am confused as to what to do and if I am interpreting the question correctly.

The algorithm that decides 3-SAT just answers yes or no, satisfiable or not. It doesn't (directly) give you an assignment for the variables. You have to use the decision algorithm as a black box to find an assignment of the variables. You should try adding a something to your formula that lets you deduce the assignment of a particular variable without changing the satisfiability.


Is $f(cn)$ always $O(f(n))$ for constant $c$ and any function $f$? This seems to be true for any function I can think of, but I'm not quite sure how to prove it. Is there a proof of this proposition for any such function or a counter-example?

First, let us note that for monotone $f$, the statement holds for some $c > 1$ iff it holds for all $c > 1$. Indeed, let $1 < c_1 < c_2$. If the statement holds for $c_2$ then $f(c_1n) \leq f(c_2n) = O(f(n))$ due to monotonicity. In the other direction, let $M$ be an integer so that $c_2 \geq c_1^M$. Then induction shows that $f(c_1^Mn) = O(f(n))$, and so $f(c_2n) = O(f(n))$ due to monotonicity.

If $f$ is a polynomial then $f(n) = \Theta(n^A)$ and so $f(cn) = \Theta((cn)^A) = \Theta(n^A) = \Theta(f(n))$. A similar argument works when $\Omega(n^{A-o(1)}) \leq f(n) \leq O(n^{A+o(1)})$.

In the other direction, suppose that $f(n) = n^{g(n)}$, and suppose that $g(n)$ is nondecreasing. Then $f(cn) \geq c^{g(n)} f(n)$, and so $f(cn) = O(f(n))$ iff $g(n)$ is bounded. So in some sense, if $f(cn) = O(f(n))$ then $f$ must have polynomial growth.


A basic question about approximation algorithms for the Traveling Salesman Problem Approximating the traveling salesman problem (TSP) within a constant factor $k$ is hard.  The standard proof shows that the existence of such an approximation allows the Hamilton Cycle problem to be decided.  This standard proof is discussed in many places including accepted answers on cs.stackexchange here and here.

Briefly, the standard proof for $k=2$ works as follows.  Suppose a graph $G$ with $n$ vertices is given as input to the Hamilton Cycle problem.  We create a weighted complete graph $H$ with the same $n$ vertices as follows: The edges in $G$ are given weight 1, and the added edges are given a large weight, say $n+2$.  Notice that every Hamilton cycle in $H$ either has total weight $n$, or at least $(n-1) + (n+2) = 2n+1$.  This gap allows a 2-approximation algorithm for TSP to answer the decision problem.  More specifically, if $G$ has a Hamilton Cycle, then the 2-approximation algorithm must return the value $n$ since the other Hamilton cycles have total weight $>= 2n+1$.  On the other hand, if $G$ does not have a Hamilton cycle, then the 2-approximation algorithm will return a value larger than $n$.

I'm uncertain about something even more basic.  What would a 2-approximation algorithm return if we did not add the edges of weight $2n+1$?  In other words, suppose we take graph $G$ and create a weighted graph $G_1$ by assigning weight 1 to each edge in $G$, and we do not add any new edges.  In this case, the Hamilton cycles in $G_1$ (if any) all have total weight $n$, and they all correspond to Hamilton cycles in $G$.  There is no gap in the total weights of the Hamilton cycles.

What exactly would the 2-approximation algorithm return if $G$ has a Hamilton cycle?  And what if $G$ does not have a Hamilton cycle?

The misunderstanding comes from two variations of the TSP problem:

The input graph is complete.
The input graph is arbitrary.

The standard proof above must assume the first variation of TSP.  Thus, there is no k-approximation algorithm for the first variation unless $P=NP$.  The same result then follows for the second variation due to the fact that the second variation generalizes the first variation.

To answer the question directly: The input to the TSP variation in question must be a complete graph.

Note: The Wikipedia article states the following: Often, the model is a complete graph (i.e. each pair of vertices is connected by an edge).  If no path exists between two cities, adding an arbitrarily long edge will complete the graph without affecting the optimal tour.


A data structure for holding numbers in 2 sets, using BST? Design a data structure for holding numbers in two sets:

Init - initiate the DS with two empty sets. O(1)

Insert(a,S) - insert number a to set S (S could be X or Y). O(log(n)). (n is the total number of numbers in the DS)

Find - find a number a in the DS such that the number of numbers in X that are smaller than a equals the number of numbers in Y that are bigger than a, if exists such number. O(1)

My attempt is using 2 augmented balanced binary search trees, each one presents set X or Y, insert into it the new number and saving in each node information for finding what is the number of numbers in X that are smaller than this node and the number of numbers on Y that are bigger than that node.

But given that information how could I implement the Find procedure in O(1)? Or maybe someone have better design (preferably using augmented BST)?

Since it's your exercise, I don't want to prevent you from finding the solution on your own, but I'll give you some possible hints:

Big hint:

   You can do some work during the Insert operation to make any subsequent Find run fast.

Think about that one for a while.

If you're still stuck, here are some more specific hints.  I recommend you think about each one for 15 minutes or more before moving on to the next one.

Hint #2:

   Suppose you wanted to implement an operation InsertAndFind(a,S), that effectively does Insert(a,S) followed by Find().  Could you make that run in O(log n) time?

Hint #3:

   It would also be possible to have a single data structure (e.g., a single augmented balanced binary search tree), with some information in each node.

Hint #4:

   What information would you want to keep in a node, to determine whether that node is something that could be returned in response to a future Find query?


Approximating unique string occurrences using a small, fixed amount of memory Is there a small-memory way to estimate how many unique strings have been encountered without needing to know the strings themselves?  The trick is that we only have a tiny amount of memory to track what strings we have seen.  Tiny like a 64 bit integer or 64 byte string. (The EZ infinite-memory solution is to keep a hash of the strings.)  The strings being tracked themselves can be very long.

To make sure "unique" is clear, let's say we receive four strings: "cat", "dog", "cow" and "cat".  We would count that as three unique strings as "cat" appears twice.

This method can be lossy!  Some hashing solution with collisions is perfectly acceptable.  Ideally the solution is more accurate for smaller amounts.  E.g. counting 2 unique strings, we can be pretty sure it's exactly 2, but if the method returns 200, that's probably a decent estimate. .

The partial solution I have been considering is:

Set the tracker value to 1
Set the counter value to 0
For each string, get its hash value.  If the tracker number is not evenly
divisible by the hash, then increment the counter and multiply the
tracker by the hash

The problem is that the tracker will quickly overflow and that will then (I assume) affect what numbers evenly divide it.

Your problem is known as the count-distinct problem. The Wikipedia page describes some of the algorithms which have been designed for this problem.


Placing small circles randomly inside a larger circle, where no two small circles intersect Sorry if this is the wrong place to ask, was unsure...let me know if it belongs some where else.

So i am trying to work out a way to write an algorithm to place a series of small circles of a set radius (all the small circles have the same radius), inside a larger circle.

The small circles cannot overlap each other or overlap the main circle's perimeter, and they are placed randomly inside the main circle.

I am wanting it to then populate as many circles as it can until it is not possible to place any more circles without overlapping another.

This obviously means that each run through depending on the random placements will potentially give different amounts of maximum number of circles inside the big circle - thats fine, and thats some what the point.

Does any one have any advice how i might approach the logic for this?

Suppose the small circles have radius $r$, and the large circle has radius $R$.  If there are less than, say, 100 small circles, then the following simple algorithm should be fast enough:

Generate a larger number, say 1000, of points at random locations inside a circle of radius $R-r$ (this smaller radius guarantees that a small circle centered at each point will fit within the radius-$R$ circle).
Calculate all roughly 500000 pairwise distances between points.
Sort these distances in increasing order.
Loop through the distances.  For each distance $< 2r$, randomly pick either point and delete it.  (Such a distance implies that there could not be a radius-$r$ circle at both points without overlap.)  If the distance refers to a point that has already been deleted, ignore it.
All points that remain are at least $2r$ apart from each other, so you can put a radius-$r$ circle at each.

If this is too slow, you could use a grid to speed things up: Make the step size of the grid $2r$, and only bother comparing point pairs that are in the same grid cell or adjacent grid cells.  (Every pair of points $x \in X, y \in Y$ for 2 non-adjacent grid cells $X$ and $Y$ is at least $2r$ apart, so we don't need to bother testing them.)

NOTE: This could leave holes where a small circle could fit.  My intuition is that having enough initial potential centre points will make this unlikely.  You could use a smaller grid, of step size $r$, to find some (not necessarily all) of these holes: A grid cell that does not overlap any circle is definitely a "hole" (a circle can be added there).

In case you're wondering, the problem you "really" want to solve is to find an independent set of vertices in a graph in which you have a vertex for each circle and an edge between 2 points whenever they are at distance $< 2r$.  The general form of this problem is NP-hard, though I suspect there is enough additional structure here that a faster solution (maybe poly-time, maybe not) is possible.


Unrolling multi-variable mu (μ) expressions in type theory Unrolling an iso-recursive μ-type expression such as, say, one isomorphic to natural numbers:

μα.1+α

using

unroll : μα.T → T[μα.T / α]

by three steps, for example, gives:

μα.1+α
μα.1+(1+α)
μα.1+(1+(1+α))
...

If I instead have a polymorphic list, such as:

λα.μβ.1+αβ

is there a necessary relative order to the expansion of λ and μ? Say I instantiate α to T:

μβ.1+Tβ
μβ.1+T(1+Tβ)
μβ.1+T(1+T(1+Tβ))
...

Can we instead unroll μ before applying the λ at an arbitrary step?

λα.μβ.1+αβ
λα.μβ.1+α(1+αβ)
λα.μβ.1+α(1+α(1+αβ))
...

It looks in this case like we could. What I'd really like to know though is how to expand an expression having more than one μ variable; say:

μα.μβ.1+αβ

I could start with a few unrolls with β:

μα.μβ.1+αβ
μα.μβ.1+α(1+αβ)
μα.μβ.1+α(1+α(1+αβ))
...

...starting with α instead looks more complicated:

μα.μβ.1+αβ
μα.μβ.1+(μβ.1+αβ)β
μα.μβ.1+(μβ.1+(μβ.1+αβ)β)β
...

...or maybe α-β alternation could work, say starting with β:

μα.μβ.1+αβ
μα.μβ.1+α(1+αβ)
μα.μβ.1+(μβ.1+αβ)(1+(μβ.1+αβ)β)
...

...or starting with α:

μα.μβ.1+αβ
μα.μβ.1+(μβ.1+αβ)β
μα.μβ.1+(μ(1+αβ).1+α(1+αβ))(1+αβ)
...

Where does it all end? I can't imagine they end up equivalent. Is there a standard approach?

I can't image they end up equivalent.

That's where you're wrong! In fact, starting with two different unfoldings of some expression you can always keep unfolding them in such a way that they "meet" again.

This property is formally called confluence.

More formally: define

$$ T \rightarrow_\tau T'$$

If $T'$ is the result of a repeated number of unfoldings of $T$. We have the following Theorem:

Suppose $$ T_1\ {}_\tau\!\leftarrow T\rightarrow_\tau T_2$$

There exists $T_3$ such that $$ T_1\rightarrow_\tau T_3\ {}_\tau\!\leftarrow T_2$$

The proof is a bit subtle. I'll just try and convince you using your own example: $$T = \mu\alpha\beta. 1 + \alpha\times\beta$$

The reductions you outlined contain a slight mistake, the correct "$\alpha$-reduction" is:

$$T\rightarrow_\tau \mu\beta.1 + T\times \beta\qquad (1)$$

and not $T\rightarrow_\tau \mu\alpha\beta.1 + (\mu\beta.1+\alpha\times\beta)\times\beta$ As you suggest.

The $\beta$-unfolding is:

$$T\rightarrow_\tau \mu\alpha.1+\alpha\times(\mu\beta.1+\alpha\times\beta)\qquad (2)$$

Let's show both of these lead to the same term. Take $U(\alpha)=\mu\beta.1+\alpha\times\beta$. We have
$$ T\rightarrow_\tau \mu\alpha.1+\alpha\times U(\alpha)$$
By the above reduction. Set $T_1=\mu\alpha.1 +\alpha\times U(\alpha)$. On the other hand
$$T\rightarrow_\tau 1+ T\times U(T)\qquad (3)$$

by composing (1) with a $\beta$-unfolding. Composing the second reduction with an $\alpha$-reduction gives
$$ 1 + T_1\times U(T_1)$$

But since $T\rightarrow_\tau T_1$, we can replace $T$ by $T_1$ in (3) to get identical terms.


Example of non-regular context free language L such that prefix(L) is regular Suppose we have some non-regular context free language L. Suppose we also have language of all prefixes of words in L.

  What can be an example of non-regular language L such that language of
  it's prefixes is regular (Can be represented by a finite automaton)?

I don't understand how language of prefixes can ever be regular, since the set of
 prefixes of a word include the word itself.

For example $L= a^nb^n$ is my non-regular language.
The language of it's prefixes would include : $\epsilon,a^n$ where $n\ge 1$,$a^nb$ where $n\ge 1$ etc...

But what about b's ? We need to know how many a's there were in the first place. Therefore I don't see how the language of prefixes can be regular.

Consider the language of words with the same number of a's and b's. It is non-regular but the set of prefixes is the set of all words which clearly is regular.


Why does $W[1] = A[1]$ hold? By definition, a parameterized problem $(Q, \kappa)$ is in $W[1]$ if it can be transformed into a combinatorial circuit $\varphi$ in polynomial time, such that the weft of $\varphi$ is 1.

On the other hand, $(Q, \kappa) \in A[1]$, if it can be transformed into a parameterized model checking problem $p$ -$MC(\Sigma_1)$.

Finally, $(Q, \kappa) \in W[1] \Leftrightarrow (Q, \kappa) \in A[1]$ holds.
However, I did not see why a parameterized model checking problem has to have weft 1. It occurs to me as if $W[1] \subseteq A[1]$.

Why are they the same class?

The proofs can be found in the literature. I'll try to explain the intuition.

The short version is that parameterized independend set is typical for both $W[1]$ and $A[1]$.

The general intuition about the $W$- and the $A$-hierarchy is that they are about amounts of nondeterminism. In particular, at the first levels, both hierarchies allow existential nondeterminism with $n^k$ possibilities to choose from, followed by universal nondeterminism with $n$ possibilities, followed by existential nondeterminism with a constant number of possibilities. Let us see that for each of the three problems.

Independend set is the question:

Is there a set of $k$ vertices,
such that for all edges
there is an endpoint not in the set?

The first bullet point is existential ("is there?") with $\binom nk$ possibilities. Up to parameterized reductions there is no difference between $\binom nk$ and $n^k$. The second point is universal ("for all") with as many possibilities as there are edges. Which is bounded by the input size $n$. The last part is existential ("there is") with $2$ possibilities ($2$ endpoints per edge).
In the case of $W[1]$, that is of parameterized weighted $c$-CNF-SAT, the first existential nondeterminism concern the set of variables to set to true, much like the vertex set above. The universal nondeterminism ranges over the clauses, all of which have to be satisfied. Their number is bounded by $n$. The last part is existential, namely finding an atom in the clause that is satisfied. That part has at most $c$ possibilities.
For model checking of $\Sigma_1$, it is not obvious at first that the above nondeterminism suffices. We will have to do some normalization of $\Sigma_1$ formulae. First, let us assume that the quantifier-free part is in DNF. Achieving DNF may bring an exponential blow-up, but as the formula is the parameter, any blow-up is fine. Second, let there be a bound $r$ on the arity of relations (I will not go into the details of how to do that). Last, let all atoms be negative (that can be achieved by adding complements for all relations with an $n^r$ blowup.

Now the quantifiers incur existential nondeterminism with $n$ possibilites each, for a total of $n^k$. The disjunctive part of the DNF brings another existential $n$. The resulting $n^{k+1}$ is as well as $n^k$ under parameterized reductions. Then comes a conjunctive clause for universal nontederminism with $k$ possibilities. Then comes a negated relational atom: For all tuples in the relation ($n$ (universal) possibilities, because the relation is part of the input) there is some position ($r$ existential possibilities) at which the tuple differs from the values chosen for the quantifiers. Again, think of independent set, where $r=2$. The universal part totals to $k\cdot n$, which is as well as $n$ under reductions.


Wifi throughput calculation I have a problem which i don't know how to calculate or more specifically what am I missing. The subject is about 802.11 (wifi)

The selected PHY rate is 54Mbit/s, that is whenever DATA is being sent the rate is 54Mbit/s, and when the node is not sending anything the rate is 0. To simplify the task, assume that there are no collisions and no errors in the channel.

The frames in the figure are marked up as follows:

Message Purpose Duration, us RTS Request to send 44 CTS Clear to send 48 DATA Payload packet Variable ACK Acknowlegement 44 SIFS Inter-frame-spacing 4 DIFS Same as SIFS 16 Backoff MAC arbitration 0..63

The question is: What would be average effective throughput (in Mbit/s) with basic signaling if the DATA packet takes 166 microseconds? Write your answer as average effective bit rate for whatever is being put into DATA packets. Allowed error is 2%

What am I missing?

Okay so I managed to solve it.

It was simply: PHY rate * (DATA time / Access cycle time, where backoff = 30us)


Uniform Convergence and VC Theroy I've started reading more about statistical learning theory, specifically this paper right here and I cannot understand the following part:

  It turns out the conditions required to render empirical risk
  minimization consistent involve restricting the set of admissible
  functions. The main insight of VC (Vapnik-Chervonenkis) theory is that
  the consistency of empirical risk minimization is determined by the
  worst case behavior over all functions f ∈ F that the learning machine
  could choose. We will see that instead of the standard law of large
  numbers introduced above, this worst case corresponds to a version of
  the law of large numbers which is uniform over all functions in F

The part that is in bold is what I do not get. This part specifically: "Consistency of ERM is determined by the worst case behavior over all functions in function space F, that learning machine could choose". What is exactly meant by the worse case behavior? I tried looking into VC theory and could not find the answer.

What is considered in VC theory is about the bound of error between empirical risk and real expected risk. Hence, the worst-case function is when the difference between these two risks is maximized.


Is the inverse of MST cut property true? Why? If we partition the nodes of a graph into sets A and B, there is an edge e of weight larger than any other edge crossing the cut between A and B, e would never be in the minimum spanning tree?

This is not the case.
If an edge $e$ is a bridge in the graph, then every MST has to include $e$. There can exist some cut in which $e$ is the heaviest edge, but this does not change the fact that $e$ must be included (there is some other cut in which $e$ is the only - and therefore the lighest - edge).


Complexity of simplifying two-variable algebraic expression Given algebraic expression of two variables x and y, I want to simplify this algebraic expression until it cannot be simplified anymore.  What algorithm can I use for this?

For instance:

x+x+y+y = 2•x+2•y = 2•(x+y)

x•x+y•y=x2+y2

(x+y)•(x+y)=(x+y)2

x•x+x•y+x•y+y•y=x2+2•x•y+y2=(x+y)2

The most simplified algebraic expression is the one with the fewest characters.  Expressions will have only addition, multiplication, and exponentiation with a constant.

What is the complexity of this problem?

Does exist polynomial time and space algorithm to solve this problem? I tried to find over the Internet the algorithm to simplify algebraic expressions, but I didn't find anything.
The problem is that I don't know where to start.

Minimizing the number of characters is a tough one.

The field of symbolic computation might be relevant, but I don't know of any algorithms that find a simplified form with the fewest characters.

Here's one approach you can use, that won't be optimal.  Express the expression as a polynomial over variables $x,y$.  Then, factor the polynomial.  Computer algebra systems will include algorithms to do that for you.  For the size problems you are talking about, this should be very efficient.

This won't necessarily find the optimal expression.  For instance, $x^2 + y^2 + 2xy + 1$ is irreducible (can't be factored), but there is a shorter equivalent expression, namely $(x+y)^2 + 1$.  However, in many cases it will find a way to simplify the expression to some extent.

Another approach, which also isn't optimal, is to use a template-based method.  Suppose you have a "template" for what you expect the simplified expression might look like: e.g., you are interested in expressions of the form

$$T(x,y) = \sum_{j,k} a_{j,k} (b_{j,k} x + c_{j,k} y)^k + \sum_{j,k} d_{j,k} x^j y^k.$$

Then given an expression $f(x,y)$, it is possible to determine whether there is an equivalent expression of the form above.  In particular, pick many random values $(x_i,y_i)$, evaluate the expression $f$ at each of those values, and set up one equation per value

$$f(x_i,y_i) = T(x_i,y_i).$$

Here since we can evaluate $f(x_i,y_i)$, the left-hand side of each such equation is a constant.  Expanding out the definition of $T(x_i,y_i)$, the right-hand side is an expression in the unknowns $a_{j,k},b_{j,k},c_{j,k},d_{j,k}$.  Thus, each value $(x_i,y_i) we pick gives us one equation on those unknowns.  After sufficiently many equations, it should be possible to solve that system of (nonlinear) equations for the unknowns.  (Computer algebra packages typically also include methods to solve a system of nonlinear equations for you.)  There may be many solutions, in which case you could enumerate all solutions, or consider simpler templates and find one solution per template.

This might give you multiple candidates for simplified expressions, and you can keep the one that has the fewest characters.  Again, there will be cases where it is not the optimal solution, but it might be useful for small expressions.

Finally, if you care about optimality more than efficiency, you could enumerate all expressions in order of increasing length, and test each one to see if it is equivalent to the original expression.  A simple way to test whether two expressions are equivalent are to evaluate them at some randomly selected points; this is fast, but might occasionally err on the side of failing to realize that two inequivalent expressions are inequivalent.  A more comprehensive test is to convert both expressions to polynomials, then check that their coefficients are equal.  This should give the optimal solution, but I expect it will be inefficient: the running time is exponential in the length of the solution.