Why run -time of N-Queens using backtracking algorithm fluctuates? I have tested and measured the running time of a backtracking algorithm for solving the $N$-Queens problem. When $N=7$, the run time is $0.773$, but for $N=8$, the run time is $0.492$.

I think the run time should grow exponentially with the size of $N$.
Why is the algorithm slower for $7$ than for $8$?
This case also happens between $20$ and $21$ ,$28$ and $29$.
This is my pseudocode.

Function BACKTRACKING-SEARCH(csp)returns a solution,or failure
   return BACKTRACK({},csp)
Function BACKTRACK(assignment, csp) returns a solution, or failure
begin
if assignment is complete then return assignment
var = SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp],assignment,csp)
for each value in ORDER-DOMAIN-VALUES(var, assignment, csp) do
if value is consistent with assignment then
add {var = value} to assignment
Result ←BACKTRACK(assignment,csp)
If Result ≠ failure then
return Result
Remove {var=value} and inferences from assignment
End if
End for
Return failure
end

Consider that there might be something wrong with your experimental setup. The theoretical running time of an algorithm is based on an ideal model of a computer, but in practice there are lots of non-ideal behaviours. The running time of an experiment can vary based on lots of factors, and will be different from run-to-run.

You should repeat the experiment a number of times, and take the average running time of those runs to get a reliable reading. You could also compute the standard deviation of the running time, so you can get a good idea of whether the observed difference is statistically significant.

I implemented a straightforward backtracking approach to enumerate all solutions to the $n$-queens problem. The running time, taken as an average over 10,000 runs, was 0.045 ms for $n=7$, and 0.22 ms for $n=8$. This nicely fits with the fact that the number of (partial) solutions explored was 552 for $n=7$, and 2057 for $n=8$ (we have that $\frac{2057}{552}\times0.045\times\frac{8}{7}=0.19\approx 0.22$). So, based on my data, there is nothing that suggests $n=8$ is faster than $n=7$ -- if we want to enumerate all solutions.

Keep in mind that it is really hard to measure very low running times. There are other processes running at the same time, and how these are scheduled may affect the running time of your process. Your operating system may preempt your process for a while to run another process. For best accuracy, you should measure CPU time rather than "wall time", so that the time that your process is preempted is not taken into account.

If you're doing only a single run, the 0.773 or 0.492 (seconds?) you are measuring probably isn't the time required to do the backtracking (since that takes less than a millisecond), it's the time required to launch the process and load the executable from disk. The magnitude of the thing you're measuring is very small compared to the magnitude of the noise.

For completeness, here are my results for $n=1$ to $14$, giving the total number of valid partial solutions, the number of valid complete solutions (with $n$ queens), the first time (i.e., after how many partial solutions) a complete solution was found, average running time in ms, number of runs the average was taken over and the minimum/maximum number of timer ticks for a single run (to show how wide the spread in measured running times is).

n=1     total: 2        valid: 1        first: 2        0,0003ms        runs: 10000     min/max: 0/868
n=2     total: 3        valid: 0        first: -1       0,0006ms        runs: 10000     min/max: 0/55
n=3     total: 6        valid: 0        first: -1       0,0006ms        runs: 10000     min/max: 0/45
n=4     total: 17       valid: 2        first: 9        0,0009ms        runs: 10000     min/max: 1/96
n=5     total: 54       valid: 10       first: 6        0,0018ms        runs: 10000     min/max: 3/167
n=6     total: 153      valid: 4        first: 32       0,0071ms        runs: 10000     min/max: 15/286
n=7     total: 552      valid: 40       first: 10       0,0492ms        runs: 10000     min/max: 131/765
n=8     total: 2057     valid: 92       first: 114      0,2412ms        runs: 10000     min/max: 703/3107
n=9     total: 8394     valid: 352      first: 42       1,1385ms        runs: 2635      min/max: 3393/7416
n=10    total: 35539    valid: 724      first: 103      5,5285ms        runs: 543       min/max: 16869/29597
n=11    total: 166926   valid: 2680     first: 53       30,03 ms        runs: 100       min/max: 91033/116218
n=12    total: 856189   valid: 14200    first: 262      172,61ms        runs: 18        min/max: 543521/593573
n=13    total: 4674890  valid: 73712    first: 112      1037,2ms        runs: 10        min/max: 3379429/3490449
n=14    total: 27358553 valid: 365596   first: 1900     6736,1ms        runs: 10        min/max: 21845050/23117728

If we consider purely the time until finding the first solution, then the running time no longer is strictly increasing, but certain $n$'s are ``easier'' to solve in the sense that the backtracking strategy used happens to come across a valid solution earlier:

n=1     total: 2        0,0005ms        runs: 10000     min/max: 0/1199
n=2     total: 3        0,0005ms        runs: 10000     min/max: 0/50
n=3     total: 6        0,0004ms        runs: 10000     min/max: 0/50
n=4     total: 9        0,0004ms        runs: 10000     min/max: 0/56
n=5     total: 6        0,0004ms        runs: 10000     min/max: 0/44
n=6     total: 32       0,0016ms        runs: 10000     min/max: 2/64
n=7     total: 10       0,0006ms        runs: 10000     min/max: 1/54
n=8     total: 114      0,0089ms        runs: 10000     min/max: 21/232
n=9     total: 42       0,0033ms        runs: 10000     min/max: 7/199
n=10    total: 103      0,0107ms        runs: 10000     min/max: 29/140
n=11    total: 53       0,0052ms        runs: 10000     min/max: 14/77
n=12    total: 262      0,0533ms        runs: 10000     min/max: 138/2867
n=13    total: 112      0,0192ms        runs: 10000     min/max: 51/228
n=14    total: 1900     0,4925ms        runs: 6091      min/max: 1375/3820
n=15    total: 1360     0,3772ms        runs: 7953      min/max: 1072/3057
n=16    total: 10053    3,1402ms        runs: 956       min/max: 8997/17103
n=17    total: 5375     1,7544ms        runs: 1710      min/max: 5040/13332
n=18    total: 41300    14,813ms        runs: 203       min/max: 45021/60028
n=19    total: 2546     0,9637ms        runs: 3113      min/max: 2753/8341
n=20    total: 199636   83,5  ms        runs: 36        min/max: 264863/288246
n=21    total: 8563     3,9   ms        runs: 770       min/max: 11193/18734
n=22    total: 1737189  953,3 ms        runs: 10        min/max: 2900112/3477819
n=23    total: 25429    15,342ms        runs: 196       min/max: 41098/116394
n=24    total: 411609   251,833ms       runs: 12        min/max: 803905/970462
n=25    total: 48684    31,6211ms       runs: 95        min/max: 92880/133684

The total column reports the number of partial solutions considered before a valid complete solution is found (or the total number of partial solutions considered if there do not exist valid complete solutions). You can see that (for instance) when $n$ goes from 20 to 21 there is a large drop in number of solutions that need to be considered (and consequently a large drop in running time).

In this case, my backtracking algorithm (which uses the most obvious approach of starting at the top left, recursing, and moving the queen in each row from left to right), contrary to yours, takes longer to find a solution for $n=8$ than it does for $n=7$. However, the spread in running times (even though the algorithm is completely deterministic) is large: the fastest $n=8$ solution is more than twice as fast as the slowest $n=7$ solution.

It is difficult to quantify why a certain $n$ is more ``lucky'' than another, because this requires a deep understanding of the structure of the search space and how it interacts with a particular backtracking strategy.

One interesting fact is that if $n$ is odd, there always exists a solution placing a queen in the top left corner. This leads to the observation that the time to find the first solution for $2n+1$ is always much faster than that for $2n$, because the algorithm's guess (in the $2n+1$ case) for the first queen (top left corner) is always correct and the problem then reduces to solving a restricted version for the $2n$ case where no queens can be placed on the diagonal.


Should your heuristic for an A* search algorithm be the same scale as your actual weights? I'm a bit confused about the scale of heuristics for implementing A* search. $f(n)$ is the total cost of travelling to a node $n$. It is calculated by $f(n) = g(n) + h(n)$. $g(n)$ is the cost of the path to node $n$ from the source node. $h(n)$ is a heuristic function that estimates the cost of the cheapest path from n to the goal. (Roughly summarised from the wikipedia article on A*)
My question is should $h$ and $g$ be on the same scale? e.g. if g(n) to node n is 10 is it ok if the h(n) is 800?
I've read some conflicting takes on it where one example of using A* for plane routes had $g$ values in the range of 10-50 but $h$ values in the range 100 - 900 but elsewhere I read that they should be the same scale to avoid changing an A* search into a greedy best first search?

I think you might have misunderstood the heuristic function.  It is supposed to give an underestimate on the distance from a node $n$ to the goal node $t$.  The closer this estimate is to the true value, the better A* will perform.
The only criterion for the heuristic function is that it never gives a higher value for $h(n)$ than the true cost of going from $n$ to $t$.
Let $\text{dist}(a, b)$ be the "true" distance from $a$ to $b$, and let $\text{dist}_0(a,b)$ be an underestimate (e.g. the Euclidean distance from $a$ to $b$ if you have a map).
If you are searching for a path from $s$ to $t$,
then $g(n)$ is defined to be $\text{dist}(s, n)$, whereas $h(n)$ is $\text{dist}_0(n, t)$.  So
$$ \text{dist}(s, n) + \text{dist}_0(n, t) = g(n) + h(n) = f(n).$$
There is nothing about scale of $g(n)$ and $h(n)$, except that $h(n)$ must give a lower value than (or equal to) the true distance from $n$ to $t$.


Given a binary tree $t$, prove that $size(t) < 2^{h(t)}$ I was able to prove that $size(t) \leq 2^{h(t)} - 1$ for any binary tree $t$, however I wasn't able to do anything reasonable with this statement.

I know it's a proof by induction and that the inductive hypothesis is the following:

$
size(l) < 2^{h(l)} \\
size(r)  < 2^{h(r)}
$

where $l$ and $r$ are the left and right subtrees of the tree $t = \langle l,v,r \rangle$. Usually what I'd do is start from $size(\langle l,v,r \rangle)$ and work my way up to $< 2^{h(\langle l,v,r \rangle)}$. However I wasn't able.

If a binary tree has height $h$ then it has at most 1 node at depth 0, at most 2 nodes at depth 1, ..., at most $2^{h-1}$ nodes at depth $h-1$ (the maximal depth), and so at most $1+2+\cdots+2^{h-1} = 2^h-1$ nodes in total.

You can also prove this by induction. When $h=1$, the tree consists only of a root, so at most $1=2^h-1$ vertices. Given a tree of height $h$, its two subtrees have height at most $h-1$, and so together contain at most $2(2^{h-1}-1)$ vertices. Together with the root, the tree contains at most $2(2^{h-1}-1)+1=2^h-1$ vertices.


Calculating the probability of data loss of a RAID 1+0 system I have a task where a RAID 1+0 system (A RAID 0 connects two RAID 1's with two disks each = makes 4 disks in total) is given with no further details. Then let p be the probability that one disk shows signs of failure. The variable p is not further defined.

Now I've received the task to calculate the probability that there will be a data loss in this RAID 1+0 system and I have literally no idea how solve this. I know that RAID 1+0 systems can cope with failure of the 1st and 3rd disk without having any data loss.

Please enlighten me, thanks!

A RAID 1 system with two disks fails if both disks fails. If each disk fails with probability $p$, then this happens with probability $p^2$.

The RAID 1+0 system fails if any of the two RAID 1 component systems fails. Since each of them fails with probability $p^2$, the probability that either fails is $2p^2 - p^4$ (using inclusion-exclusion).

In symbols, let $x_1,x_2,x_3,x_4$ be the failure status of the disks, that is, $x_i$ is true if the $i$th disk failed. The entire system fails if
$$ (x_1 \land x_2) \lor (x_3 \land x_4). $$
The variables $x_1,x_2,x_3,x_4$ are independent $\mathrm{Bernoulli}(p)$ random variables. A short calculation (given above) shows that
$$ \Pr[(x_1 \land x_2) \lor (x_3 \land x_4)] = 2p^2 - p^4. $$

You can solve all similar questions in the same way.


What is the definition of Computer Science, and what is the Science within Computer Science? I am pursuing a BS in Computer Science, but I am at an early point of it, and I am pretty sure I will be happy with my choice given that it seems like an academically and career flexible education to pursue.

Having said that, there seems to be a variety of definitions about what Computer Science really is in respects to academia, the private-sector, and the actual "Science" in "Computer Science" I would love to have answers(Or shared pondering) as to the breadth of things an education in Computer Science can be applied to, and ultimately the variety of paths those within Computer Science have pursued.

Computer science is a misnomer - there is actually no "science" in computer science, since computer science is not about observing nature. Rather, parts of computer science are engineering, and parts are mathematics.

The more theoretical parts of computer science are purely mathematical. For example, what is a good algorithm for sorting? How do we define the semantics of programming languages? How can we be sure that a cryptographic system is secure?

When computer science gets applied, it becomes more like engineering. For example, what is the best way to implement a matrix multiplication algorithm? How should we design a computer language to facilitate writing large programs? How can we design a cryptographic system to protect online banking?

In contrast, science is about laws of nature, and more generally about natural phenomena. The phenomena involved in computer science are man-made. Some aspects of computer science can be viewed as experimental in this sense, for example the empirical study of social networks, the empirical study of computer networks, the empirical study of viruses and their spread, and computer education (both teaching computer science and using computers to teach other subjects). Most of these examples are border-line computer science, and are more properly multidisciplinary. The closest one gets to the scientific method in computer science is perhaps the study of networks and other hardware devices, which is mainstream in the subarea known unofficially as "systems".

These examples notwithstanding, most of the core of computer science is not science at all. Computer science is just a name - it doesn't need to make sense.

As for the scope of computer science, the best definitions is perhaps: that which computer scientists do. Computer science, like every other academic discipline, is a wide area, and it is difficult to chart completely. If you want a sampling of what people consider computer science, you can look at the research areas of your faculty.


What is the Big O of T(n)? I have a homework that I should find the formula and the order of $T(n)$ given by

$$T(1) = 1 \qquad\qquad
  T(n) = \frac{T(n-1)}{T(n-1) + 1}\,.
$$

I've established that $T(n) = \frac{1}{n}$ but now I am a little confused. Is $T(n) \in O(\frac{1}{n})$ the correct answer for the second part?

Based on definition of big-O we have that

$$O(g(n)) = \{f(n) \mid \exists c, n_0>0\text{ s.t. } 0\leq f(n) \leq cg(n)\text{ for all } n\geq n_0\}\,.$$

This holds for $f(n) = g(n) = \frac{1}{n}$ so, based on the definition, $O(\frac{1}{n})$ should be correct but, in the real world it's impossible that algorithm can be faster than $O(1)$.

Yes, all functions $f(n)$ satisfy $f(n) \in O(f(n))$. The definitions are meaningful even if $f(n)$ isn't the running time of any function. Indeed, this notation comes from number theory, where $f(n)$ is usually some error term. Even in computer science, sometimes big O notations is used while analyzing algorithms for something other than a running time or space requirements.


Is sierpenski's triangle considered to be a computational model? I was reading about sierpenski's triangle and i found that it is similar to pascal's Triangle, which can show coefficients in binomial expansion,  also rule 90 from ECA.

If Sierpenski's triangle can show coefficients in binomial expansion, and was simulated by other two systems {Pascal's Triangle} and {Rule 90} does that means it is a computationa model ?

What about rule 110, which is proved to be universal, is it a computational model also?

I would not call Sierpenski's triangle a computational model.  A computational model should be a system that has a way to compute something.  This means there needs to be a way to supply an input, and a way that the system does something with that input to compute something.  Sierpenski's triangle is a single thing (a single set), and it is fixed -- there is no way to supply different inputs and get a different output.

For similar reasons, I would not call Pascal's triangle a computational model.

However, I would call rule 90 a computational model.  There are standard ways of providing an input and computing stuff (e.g., the input bitstring is interpreted as a row, and then successive rows are derived using the cellular automaton rules, which is interpreted as a computation).  Similarly, I would call rule 110 a computational model.  Or, more generally, I might call cellular automata a computational model, and rule 90 and rule 110 as two instances of cellular automata.


Question on Predicates and Quantifiers I am reading from "Discrete Mathematics and Its applications" by Kenneth H. Rosen, 7th edition. Consider the highlighted part in the following example taken from the same book:

  Question Use predicates and quantifiers to express the system specifications “Every mail message larger
  than one megabyte will be compressed” and “If a user is active, at least one network link will
  be available.”

  Solution: Let S(m, y) be “Mail message m is larger than y megabytes,” where the variable x has
  the domain of all mail messages and the variable y is a positive real number, and let C(m) denote
  “Mail message m will be compressed.” Then the specification “Every mail message larger than
  one megabyte will be compressed” can be represented as ∀m(S(m, 1) → C(m)).
  Remember the rules of
  precedence for quantifiers
  and logical connectives!
  Let A(u) represent “User u is active,” where the variable u has the domain of all users,
  let S(n, x) denote “Network link n is in state x,” where n has the domain of all network
  links and x has the domain of all possible states for a network link. Then the specification
  “If a user is active, at least one network link will be available” can be represented by

  ∃uA(u) → ∃nS(n, available).

"Existential quantifier" ∃u is used here, So I think, it should be ∃uA(u)∧ ∃nS(n, available) in place of ∃uA(u) → ∃nS(n, available).

Generally, we use 'implication' with 'universal quantifier' as shown in ∀m(S(m, 1) → C(m)).

Please correct me, if I am wrong.

The meaning of
$$ \exists u A(u) \land \exists n S(n,\text{available}) $$
is "there exists an active user, and there exists a network link which is available". The conditioning is missing here.

If $P = \exists u A(u)$ and $Q = \exists n S(n,\text{available})$, then we are trying to model "if $P$ then $Q$", whose formal form is $P \rightarrow Q$, whereas your answer is $P \land Q$.

In particular, if there doesn't exist an active user, then $P \land Q$ is always false, whereas $P \to Q$ is always true.


Parallel algorithm for finding the maximum in $\log n$ time using $n / \log n$ processors We were presented in class with an algorithm for finding the maximum in an array in parallel in $O(1)$ time complexity with $n^2$ computers.
The algorithm was:

Given an array A of length n:

Make a flag array B of length n and initialize it with zeroes with $n$ computers.
Compare every 2 elements and write 1 in B at the index of the minimum with $n^2$ computers.
find the index with the 0 in A with $n$ computers.

The lecturer teased us it could be done with $\frac{n}{\log n}$ computers and with $\log n$ time complexity.
After alot of thinking I couldn't figure out how to do it.
Any idea?

Divide your original array into $n/\log n$ blocks of length $\log n$. Put each processor in charge of each block, and find the maximum using the usual algorithm in time $\log n$. We now need to compute the maximum of an array of length $n/\log n$. Pair up the elements and compute the pairwise maxima to reduce the size of the array by a half. Repeat it $\log n$ times to find the maximum of the entire array.

The same idea also shows that you can compute the maximum in parallel in constant time using $n^{1+\epsilon}$ computers for every $\epsilon > 0$. (Exercise.)


Online Learning Resources for Discrete Mathematics Are there any good Discrete mathematics learning web resources with problem sets?

There is a whole course being offered by Udacity*, Logic and Discrete Mathematics, which has interactive quizzes and homework assignments.

The course description is as follows:

  This course presents key concepts in discrete mathematics, specifically, elementary propositional logic and elements of enumerative combinatorics, elementary number theory, and graph theory, with partially ordered sets and lattices as a unifying concept.

*I am not affiliated with them in any way, but I have taken some of their prior courses


Graph adjacency using Hashing Consider a graph $G = (V,E)$ and the following operation

$\text{neighbour}(v_1,v_2)$: returns true if the vertices $v_1$ and $v_2$ are adjacent, and false otherwise.

I now consider two standard data structures:

Adjacency Matrix. Space complexity is $\mathcal{O}(|V|^2)$ and supports the neighbour-query in $\mathcal{O}(1)$ time.

Adjacency List. Space complexity is $\mathcal{O}(|E| + |V|)$ as far as I understand, however the neighbour-query depends on the degree size.

My question is the following:

  How can we improve these data structures using hashing? (space/time complexity in terms of $|V|$ and $|E|$)

Can we e.g. reduce the space complexity of the adjacency matrix and retain an average constant time query?

With hash the space needed is $\mathcal O(|E| + |V|)$ (depending on array size given), and the time is expected $\mathcal O(1)$, but might degrade to $\mathcal O(|V|)$ (depending on collision resolving scheme).
With minimal perfect hash the space is exactly $|E| + |V|$ of entries (of appriopriate entry size).

Minimal perfect hash will map without collisions the given set - array for $n$ elements will have exactly $n$ length, so the $|E|$ edges will occupy exactly $|E|$ array elements. Defined function $h$ will disregarding the number of entries, as opposed to normal hash which might be several times bigger than number of entries and collisions degrade the query time (as linked-list).

This is very efficient scheme for static graph, in case of dynamic one the same issue of rehashing holds. It does not matter how the nodes are encoded (string, int etc.).

How MPH works.


How to create constraints for Mixed integer linear problem? i am a beginner to Discrete optimization domain. I am working on the real world problem, i.e., Scheduling of hybrid appliances. I have hybrid appliances which can use gas and electricity or electricity and hot water or hot water and gas for their operation. Each appliance has some set of tasks, each task use above mentioned energy carriers based on the requirement.

The question is, i want to create a constraint such that if the task of the appliance starts with electricity and hot water, it should end with using electricity and hot water. It should not alter the energy carrier to gas during the operation.

I have created some of the decision variables like this:

$x_{t,i,j}$  indicates whether task j of appliance i  at time slot k processed by electricity or not; 1 = task processed; 0 = not processed

$y_{t,i,j}$ indicates whether task j of appliance i at time slot k processed by natural gas or not; 1 = task processed; 0 = not processed

$z_{t,i,j}$ indicates whether task j of appliance i at time slot k processed by hot water or not; 1 = task processed; 0 = not processed

I tried with the following constraint it seems something missing.

$\sum_{k=t}^{t+H_{i,j}}$ $(x_{t,i,j}+y_{t,i,j}+z_{t,i,j})$ $\geq$ $H_{i,j} (x_{t,i,j}+y_{t,i,j}+z_{t,i,j})$

Where
i is index of appliance.

t is current time slot.

j is index of task.

$H_{i,j}$ is run time of tasks.

You have the constraint:

$\sum_{k=t}^{t+H_{i,j}}$ $(x_{t,i,j}+y_{t,i,j}+z_{t,i,j})$ $\geq$ $H_{i,j} (x_{t,i,j}+y_{t,i,j}+z_{t,i,j})$

I presume your iteration variable is $t$. In that case this says that the amount of energy used in the task is at least the expected amount of energy based on its first slot multiplied by task length. This doesn't guarantee using correct type of energy etc.

Assuming you use all required types of energy in the first slot of the task and that you need to use exactly two of them, you should have the following:

Exactly two types of energy used in first slot:

$$x_{t, i, j} + y_{t, i, j} + z_{t, i ,j} = 2$$

If you use some energy in first slot, you need to use it until the end of the task, so in each step variable indicating use of some energy type has the same value as in the first step of the task:

$$ \forall_{t'=t}^{t + H_{i,j}} x_{t', i, j} = x_{t, i, j} $$

Same goes for $y$ and $z$ variables.


What are degenerate polygons? What are degenerate polygons? How does one check whether a given pair of polygons is degenerate or not?

A polygon is degenerate if some of its vertices lie on each other. e.g the triangle (0,0),(0,1),(0,0) is degenerate. It has 3 sides, and 3 vertices, but two of vertices repeat. It's possible to repeat a vertex multiple times (for example (0,0),(0,0),(0,0) is another degenerate triangle). By definition, checking whether a polygon is degenerate or not is easy.

But what are the uses of degenerate polygons? One application from graphic acceleration (3D drawing) is as follows:

In 3D drawing GPUs normally use triangulation to render images. The (simple) reason for using triangles is because they are simplest possible 2D objects so don't need much hardware.

If we want to draw a complex 3D image, by this GPU limitation, we have to decompose it into multiple triangles. But if we call the GPU to render each triangle separately, it would be very slow (because of the number of calls). So the triangle strip is used to reduce the number of calls to the GPU.  A good explanation of triangle strips can be found on Microsoft Documentation: Triangle Strips, also you can see the wiki for: Triangle Strip.

But the problem arises when we want to draw two separate objects in one strip. In this case degenerate triangles help. The GPU can detect the degenerate triangles and skip their drawing. So we can connect two separate strips with one degenerate triangle.

In general if we have $n$ different components, such that we already have their corresponding triangle strips, we can draw them all by just one call to the GPU. This causes to extra memory usage, but it is a trade off between the number of calls to the GPU for rendering and the overhead of using an extra, degenerate triangle.


Complexity of / best algorithm for finding the dichotomy that maximizes information gain? Suppose that $X$ is a finite set with a probability measure $P$. I want to find the subset $A \subset X$ so that the information gain of conditioning on ${A, A^c}$ is maximal. That is, I want to find $A$ that maximizes

$$H(X) -H(X|\{A,A^c\}) = H(X) - (P(A)H(A) + P(A^c) H(A^c)),$$

where $H(A)$ refers to the entropy of the conditional probability distribution so $\mu(B) = P(B \cap A) / P(A)$. (If $P(A) = 0$, then set $P(A) H(A) = 0$. In any case, it won't be a maximizer.)

Since this splits $X$ into two sets, I am calling this a dichotomy, and the question is of finding the dichotomy that produces the largest information gain.

Question: What is the complexity of this problem? (As D.W. points out below, a reasonable corresponding decision problem is - for $t \geq 0$, is there an $A$ so that information gain is $\geq t$? This decision problem is in NP, and we can ask if it is NP-hard, etc.) Is there a good heuristic algorithm for making this choice? What if I ask for an approximately, probably correct algorithm?

I am asking this question since I'm studying decision trees in machine learning and also coding theory, and this seems like a basic question in both settings.

The information gain in that case depends only on the mass of $A$, and is maximized when $P(A)=\frac{1}{2}$. This probably shows why this definition of information gain is not very interesting.

Suppose $X=\left\{x_1,...,x_n\right\}$ and $P=\left(p_1,...,p_n\right)$.

The information gain is defined as

$IG(A)=H(X)-\left(P(A)H(A)+\left(1-P(A)\right)H\left(X\setminus A\right)\right)$

Where $H(A)$ is the entropy of the random variable which takes values in $A$ with probabilities $q_x = \mathbb{1}_{x\in A}\frac{p_x}{p(A)}$.

Now lets write explicitly what is $IG(A)$:

$$\begin{align*}
IG(A)&=
H(X)+P(A)\sum\limits_{x\in A} \frac{p_x}{P(A)}\log \frac{p_x}{P(A)}+
\left(1-P(A)\right)\sum\limits_{x\in X\setminus A} \frac{p_x}{1-P(A)}\log\frac{p_x}{1-P(A)} \\ &=
H(x)+\sum\limits_{x\in A} p_x\log \frac{p_x}{P(A)}+
\sum\limits_{x\in X\setminus A} p_x\log\frac{p_x}{1-P(A)} \\ &=
H(A)+\sum\limits_{x\in A} p_x\log p_x -\sum\limits_{x\in A} p_x \log P(A) +
\sum\limits_{x\in X\setminus A}p_x\log p_x - \sum\limits_{x\in X\setminus A}p_x\log \left(1-P(A)\right) \\ &=
-P(A)\log P(A) - \left(1- P(A)\right)\log(1-P(A)).
\end{align*}$$

So setting $y=P(A)$, you seek to maximize $f(y)=-y\log y-(1-y)\log(1-y)$ in $y\in[0,1]$. Maximum is achieved at $y=\frac{1}{2}$.

The optimization problem (or corresponding decision problem) is NP-hard, meaning that unless $P=NP$, you can't find a subset $A$ which minimizes $\left| P(A)-\frac{1}{2}\right|$ in polynomial time. This problem is called the partition problem (special case of subset sum), only that now you have the constraint that the elements sum to 1. See this question for some information about the hardness of partition problem.


What exactly is a hash function? I have no idea how I managed to get this far in life without ever really grasping this but as it happens I'm still very confused on the concept of a hash function. I did some googling/wikipedia-ing, and here's what I get:

hash tables are nice because the index can be stored in a smaller array
hash functions are kind of like uniform random number generators that always have the same seed but not really (and I don't get why)

But here are the parts that are still very ambiguous to me:

Why use a hash function and not an RNG with a set seed and array size?
Why is it ok to have "collisions", which from what I understand is two keys pointing to the same index? I mean don't we rely on that stuff to be reliable?
Why do we mod with array size at the end? Can't we just restrict the range of the hash function?
what is the difference between a hash table and a pointer?
If we know the number of unique keys, why not just use direct addressing? What is so great about this uniform distribution of keys?
in the case that the number of unique keys are not known, exactly how is that calculated in the end? It seems like something really clever is supposed to happen here but short of just counting the number of entries in the table (and somehow accounting for collisions) I don't quite see it. Also, shouldn't we count the number of unique keys before even writing the hash function, since we have to determine the array size?

Thanks for any insight!

A hash function is a pseudorandom function with a constant range. Ideally, one would like two central properties:

The hash function should be easy (fast) to compute.
The probability that two inputs $x,y$ hash to the same value is roughly $2^{-n}$, where $n$ is the output length.

The second property isn't stated rigorously. There are several ways to state it rigorously:

We can consider an ensemble (collection) of hash functions, and then the probability is over the choice of the hash function.
We can consider some distribution on pairs $x,y$.

The main difference between hash functions and pseudorandom number generators is that a hash function gives a unique value for each input. This is important for applications such as hash tables and message verification:

In hash tables, a hash function is used to choose the location at which an input is put. When you search for the same input, it is important that the hash function puts you in the same location. The pseudorandom property ensures that none of the cells gets to keep too many elements.
In message verification, you are sent separately a message and its hash, and you verify the integrity of the message by comparing its hash to the one given to you. Here the pseudorandom property ensures that it is hard to cheat.

Now to address your specific questions:

Why use a hash function and not an RNG with a set seed and array size?

A hash function has the property that each input is hashed to the same value, which is important in some applications (see above).

One way to guarantee the pseudorandom property is to have an ensemble of pseudorandom functions, and choose one at random; this is like choosing a seed at random. In practice, the seed is chosen at random once and for all, since this simplifies things.

Choosing the random seed ahead of time is OK for many applications. The main drawback is that the adversary gets to see the seed ahead of time, and can use this knowledge to try to cheat. When the hash function is easy to "break", this can actually cause problems. For example, it can allow Denial of Service attacks by sending some server some data which is all hashed to the same index, thus slowing things.

In settings when there is no adversary (say, a hash table used in your own program), a hash function with a fixed seed doesn't suffer from this drawback.

Why is it ok to have "collisions", which from what I understand is two keys pointing to the same index? I mean don't we rely on that stuff to be reliable?

Collisions are unavoidable, unless you know the input ahead of time. Indeed, if you have more potential inputs than possible outputs (which is usually the case for hash functions), then collisions are bound to occur.

Consider the idealized hash function in which the hash of any given input is chosen completely randomly (but is fixed); such a function is not efficiently computable, but otherwise is an excellent hash function. Even such a function will have collisions. The goal in constructing a hash function is to imitate this behavior while keeping the function easily computable.

Why do we mod with array size at the end? Can't we just restrict the range of the hash function?

You don't want to construct a specialized hash function for each array size. Rather, you obtain such a hash function by taking a canonical hash function and then modding with the array size.

Another way to look at it is that you are restricting the range of the hash function. You constructed your hash function with restricted range by taking a canonical hash function and reducing its output modulo the array size.

What is the difference between a hash table and a pointer?

A hash table is a data structure for storing entries (whatever they are), supporting operations such as insertion, deletion, and lookup. This is rather different from a pointer.

If we know the number of unique keys, why not just use direct addressing? What is so great about this uniform distribution of keys?

Even if you know the number of unique keys in advance, you don't necessarily know what they are, and without this information you can't use direct addressing.

Even if you did have a list of unique keys in advance, it is not always easy to construct an efficient direct addressing scheme. Imagine that the input is the set of all binary trees on at most 20 vertices. How do you map such a binary tree to an integer? While such schemes are definitely possible, often it is faster to use a hash function; the overhead due to collisions is negligible compared to the cost of computing a direct addressing scheme.

In the case that the number of unique keys are not known, exactly how is that calculated in the end? It seems like something really clever is supposed to happen here but short of just counting the number of entries in the table (and somehow accounting for collisions) I don't quite see it. Also, shouldn't we count the number of unique keys before even writing the hash function, since we have to determine the array size?

If you don't know ahead of time how many unique keys you have, then you use a dynamic hash table instead of a static one. A dynamic hash table can grow in size, though this is an expensive operation. The hash table is initialized at some fixed size, and once it gets too full, it grows in size; if it gets too empty, it shrinks. For an example, look up the Python implementation of dictionaries (dictionaries are the python name for hash tables).


What is the contradiction in the proof of the halting theorem? In the standard proof of the halting theorem, you are asked to assume that a TM_0() exists that takes another TM_1() and a string W and outputs whether TM_1() halts or executes forever right on string W, right? The proof seems to be to assume that such a TM_0() exists. Now a new TM_2() is taken that takes TM_0() as input as halts if TM_0() executes forever, and executes forever if it halts. Now from what I understand such a TM_2() is supposed to mean a contradiction, which in turn implies that TM_(0) is a contradiction. I have trouble understanding how this step in TM_2() constitutes a contradiction. All these steps seem reasonable to me.

You actually have a missing detail on how the machine $TM_2$ is defined (and a bit of confusion between $TM_1$ and $TM_0$). Let's clear this up. You start by the assumption that there is a machine $TM_0$ that operates as follows. On input $x = <TM_1, w>$, the machine $TM_0$ answers "yes" whenever $TM_1$ halts on its input $w$, and $TM_0$ answers "no" whenever $TM_1$ does not halt on its input $w$.
Now we define a machine $TM_2$. On input $z = <TM_1>$ which a description of a machine, denoted $TM_1$, the machine $TM_2$ runs $TM_0$ on $x = <TM_1, TM_1>$ and returns the opposite answer of $TM_0$. In words, the machine $TM_2$ answers "no" when $TM_1$ halts on itself, and answers "yes" when $TM_1$ does not halt on itself.
To get a contradiction, consider what happens when we feed $TM_2$ to itself as an input. That is, consider the case where the input of $TM_2$ is $z = <TM_2>$. One of the following holds:

$TM_2(TM_2)$ = "yes", and so in this case $TM_0(<TM_2, TM_2>)$ = "no". Hence, by the definition of $TM_0$, $TM_2$ does not halt on itself.
$TM_2(TM_2)$ = "no", and so in this case $TM_0(<TM_2, TM_2>)$ = "yes". Hence, by the definition of $TM_0$, $TM_2$ halts on itself.

All in all, we have that by the two items above that $TM_2(TM_2)$ = "yes" iff $TM_2$ halts on itself, which is clearly a contradiction to $TM_2$'s definition (see the bolded sentence above).


Understanding non-faulting and faulting software prefetches What is the difference between a faulting and non-faulting software prefetch. I have read some material in Google but can't understand it deeply. How do we know if a software prefetch is faulting or non-faulting in practice?

A faulting prefetch is one which (as gnasher729's answer notes) generates any translation (e.g., invalid page table entry), permission, or other fault (e.g., ECC failure, data watchpoint match) associated with the access. Such a prefetch acts as if the memory location was accessed normally. For data accesses such a prefetch can be provided by software on architectures that lack prefetch instructions. (For instruction accesses, a return operation would need to be placed in the cache block reducing the amount of useful code that would fit in the block.)

By acting as a normal access, a faulting prefetch effectively guarantees that the chunk of memory will be cached (a non-faulting prefetch may be dropped under high memory use or even a TLB miss) and that its address translation will be cached. This behavior may be preferred if the address is known to be accessed in the near future, especially if a timing critical section is about to be entered.

In some RISC ISAs, a faulting data read prefetch could be provided by a simple load to the zero register. Other ISAs could preform a normal load at the cost of temporary use of a register.

Non-faulting prefetches are purely hints to hardware, allowing hardware to drop the access if it is perceived as too expensive. By avoiding faults, such prefetches can be used without concern about whether the address is valid; prefetching from a null pointer or past the end of an array is safe.
A non-faulting prefetch is purely speculative. (Some ISAs provide support for speculative, non-faulting loads. In such an ISA, non-faulting prefetches could be implemented using such a load. Since the speculative load value may be used, hardware will typically treat such as an actual access and merely suppress any exceptions.)


Is there a name for X when X bitwise OR Y is Y? I'm wondering if there is a mathematical or computer science term for a number X such that Y | X = Y? For example:
66536 | 1000 == 66536

In this case, 1000 is the "insert name here" of 66536. Perhaps there is no name for this..? I've tried searching for "bitwise OR returns itself" and other such terms but without luck so far.

I would say that $X$ is a subset of $Y$, in terms of bits set.


outside of bitcoin, how does a network negotiate what the next blockchain should be? There are two problems I see with negotiating the next block chain:

which transactions to include in the chain (because consider transaction T which has propagated through exactly 49% of the network at the time the next block is negotiated)
which proposed block to consider the next legitimate block in the chain, because even assuming all nodes have all transactions, what's to stop every node from attempting to propose the next block, thus forcing the network to attempt to propagate and resolve N different block collisions.

In bitcoin, number 2 above is easily resolved by intentionally imposing conditions on the resulting hash of the blockchain such that it is computationally difficult to derive the hash, and thus collisions (where 2 nodes propose a valid block/hash at the same time) are very rare.

Outside of bitcoin, I'm skeptical as to how new blocks are announced and agreed upon. If you have a blockchain structure where a new block should be announced at an artificial time interval of every 10 minutes (assume the network is time sync'd) then what's to stop all your nodes from attempting to propose many different next blocks all at once? In a general blockchain network that isn't bitcoin, I don't see any restriction like #2 above that reduces the ability for many nodes to come up with their own proposed blocks and to stop them from trying to announce these blocks to the network.

Also, assuming we can resolve this issue ^ and manage to negotiate which block to use as the next one in the chain, we're assuming here that the contents of all the proposed blocks are also equal. How can a network negotiate the next block if 49% of nodes contain a transaction that the other 51% of nodes do not?

Here's how Bitcoin works.  I suppose we could say that each node can "propose" a different next block.  What this really means is that each node can select a "proposed" next block and start mining to attempt to append that block to the blockchain.  Bitcoin's proof-of-work  basically creates a lottery among all of the nodes who are doing this; it's random which one will win, but there will be only one winner, and once there is a winner, everyone will know which one won.

Nothing stops dishonest nodes from attempting to "propose" many different next blocks and mine from them.  If 100% of the network is dishonest, then you're screwed anyway.  So if you want any security at all, you need to assume that at least 51% of the nodes are honest.  And the crucial part is to look at how the honest nodes will behave.

The way that a protocol works is that it specifies how an honest node should work.  If the node is honest, it will follow the protocol faithfully -- that's more or less the definition of honest, in the world of protocols.  The Bitcoin protocol specifies how an honest node should determine what transactions to include in its proposed next block: include all of the transactions that it is aware of, and that are valid.  It also provides a mechanism to help all of the honest nodes learn of all possible transactions.

So, if at least 51% of the nodes are honest, they'll all "propose" the same next block (since they're all honestly applying the same validity checks) and start mining from that next block.

What about protocols other than Bitcoin?  No one ever promised that other protocols would be secure.  No one ever promised that merely using a blockchain (a hash-chained ledger) is sufficient to ensure security.  Bitcoin is a clever combination of multiple interlocking mechanisms that work together to provide security -- the beauty and magic is in how they fit together.  If you take away some of those mechanisms and keep only others, there's no reason to expect the result to necessarily be secure.  And it's not really possible to analyze the security of an unspecified protocol, where the only information we have about it is that "it uses a blockchain but isn't Bitcoin".


The language $\{ww \mid w \in \{0,1\}^{*} \}$ is not a CFL We have proved that the language $ L = \{\omega\omega \mid \omega \in \{0,1\}^{*} \} $ is not a CFL, and we did so by using pumping lemma. And the proof is clear to me. But I thought of the following CFG:

$ G = (\{S, S_{1} \},\{0,1\},R,S)  $ where R has the following rules:

$$\begin{align*} S &\rightarrow S_{1}S_{1} \mid \epsilon \\
S_{1} &\rightarrow 0S_{1} \mid 1S_{1} \mid \epsilon \end{align*}$$

It feels like that this CFG's language should be the language $L$ that I have defined above since each substitution adds the same letter on both sides. But it can't be since we can use pumping lemma on the word $0^{l}1^{l}0^{l}1^{l}$ (where $l$ is the pumping length). So either I'm not doing the substitution incorrectly, or the CFG's language contains $L$ and has more words that I'm not seeing currently...

Can someone help me out and point out where my mistake is?

You're assuming that, when you expand $S\to S_1S_1$, the two copies of $S_1$ must be expanded in the same way, to give two copies of some string $w$. But it doesn't have to be that way.  For example, you could do
$$S\to S_1S_1 \to 0S_1S_1 \to 0 S_1 \to 01S_1\to 01\,.$$


Shortest path visiting all nodes in an unrooted tree I have a tree. This tree has no particular root (free-tree).
I want to find a path that visit all nodes. This path has to be the shortest possible.

All edges are considered to have a distance of 1.

My problem is not finding a Hamiltonian path, because I don't have any restriction on the number of times a node can be visited.

We don't know the source node of the path. The source has to be one allowing us to find the shortest path visiting all nodes.

Hint: Start from a source $s \in V$ to visit all vertices that $V$ is the set of vertices of the tree. All edges are visited twice except those which contribute to the longest path.

Then, the shortest possible path, visiting all nodes, is equal to $2 \times |E| - |P_{L}|$, where $|E|$ denotes the number of edges, and $|P_{L}|$ is the number of edges in the longest path. This can be achieved with time complexity $O (E)$.


When should you disable all interrupts in a program? Consider a machine that has nested interrupts (a higher priority interrupt can interrupt a lower priority one, the current instruction's address is saved and later restored). Why would a programmer want to disable all interrupts using instructions like x86's CLI when you know that even when your code gets interrupted it will always return to what you it was doing?

To me it looks like disabling interrupts is bad for performance because a very high priority and thus very important interrupt has to be dealt with as quickly as possible and you are stalling that by disabling interrupts.

To implement atomic routine like a semaphore, for example. When a thread call routine to gain some critical section acess, the routine needs to change the value of semaphore's variables and it must be atomic. This change cannot be interrupted otherwise other thread, or process, can use or change some values that are under some critical section. You can find more info on Andrew Tanenbaum or William Stallings book.


CFL that runs in NP-time What is an example of a context-free language that runs in NP-time? I've done searches but cant find one. Frankly, I do not know how to determine when a CFL is P or NP. Can someone tell me, please?

All context free languages can be recognized in polynomial time:

https://en.m.wikipedia.org/wiki/CYK_algorithm


FPT algorithm for point line cover In the "Covering Things with Things" paper from Langerman and Morin, they mention the BST-Dim-Set-Cover, which is a FPT algorithm for point-line-cover, at page 666.

The algorithm chooses each point p from a set S and then subdivides it into k-lines.

This can be seen as a special case of set cover. All points (each p belongs to P) are in a cartesian plane, and the algorithm needs to find if they can be covered by k lines (where each line l belongs to L). This image below clarifies it further:

My question is around what is written in the paper linked above at page 666 regarding where is p taken from: At some point during the text it says "Otherwise, the algorithm chooses an element p ∈ S'". However, further down in the algorithm it says "choose p ∈ S" (without the prime symbol).

Is p taken from S or S' (S prime)?

Thanks!

The algorithm should say "choose $p \in S'$", that is, the text is the correct version, rather than the pseudocode.

Note how the algorithm works:

$S',S_{1},\ldots,S_{k}$ form a partition of $S$ (i.e. every element of $S$ is in exactly one of $S',S_{1},\ldots,S_{k}$).
At each step it chooses which $S_{i}$ to put $p$ into.
Initially $S' = S$, and $S_{i} = \emptyset$ for all $i$.

So $S'$ is the set of points that still need to be covered, and $S_{i}$ is the set of points covering by hyperplane $i$, in some abstract sense. Thus the algorithm, at each iteration, picks an uncovered element from $S'$, and puts it in some $S_{i}$.

Interestingly, this error made it all the way to the journal version.


Recovering species from a phylogenetic tree This question is based on Problem 2 from the 'Bioinformatics contest' of 2018.

Given a phylogenetic tree $T=(V,E)$ of $n$ vertices, in which some leaves are assigned an integer color $c$ from $[1,n]$, the task is to find a coloring of the vertices $C:V\rightarrow [1,n]$ such that the subtree induced by each color is convex, i.e. there is exactly one vertex that has no parent in the induced subgraph of that color. An equivalent formulation is that the subgraphs induced by each color must be connected.

We are given that there exist a coloring meeting these constraints (there may be multiple). What is an efficient algorithm to find such a coloring?

Biological interpretation: The idea is that we're only given that some taxa (leaves in the tree) are of the same species and we do know the full ancestor tree. The assumption of convexity of a species means that each species has a common ancestor of the same species. Of course, this information isn't always sufficient to reconstruct the whole tree, but it might recover significant parts.

BONUS: So far, this is only the first case of the problem given in the contest. Observe that the above definitions remain unchanged if we replace $T$ by a DAG $D$ with a single vertex without parent (=single source DAG). Is there an efficient algorithm that solves this problem on general single source DAG's or edge-cactus single source DAG's?

I present an algorithm for the tree case. The algorithm solves the problem in two 'passes' through the tree: first from leaves to root, then from the root to the leaves.

Algorithm:
First, we augment our tree $T$ with the additional field $v.subcolors$ for each vertex $v$. This field should contain the set of all colors present in the subtree rooted at $v$ (with $v$ included).

We traverse the tree 'layer by layer' from leaves to the root: Our first layer consists of all leaves. The next layer is constructed by taking the set of parents from all vertices in the current layer, which we repeat until we reach the root.

Then, we fill in the field $v.subcolors$ for all vertices $v$ in our layer. This is easy to do, as we know that $w.subcolors$ is already set for all children of $v$, as those belong to the previous layer we've already visited.

Observe that some vertex $v$ must be of color $c$ if and only if it separates two vertices of color $c$, i.e. it lies on the (unique!) path between two vertices of color $c$. We can determine whether $v$ separates some vertices easily if we know what colors lie in the components formed by removing $v$ from the tree: if the color $c$ lies in two distinct such components, $v$ must separate some vertices in those components.

We can efficiently find the colors in the subtree of the children of $v$, as that is given by $v.subcolors$. The parent of $v$ is a bit more tricky. However, if the parent has already been colored with color $c$, $v$ can be a separator of some vertex the component of the parent only if that vertex has color $c$! Otherwise, if there were some other color $c'$, the parent of $v$ would also separate those vertices. But the parent has color $c$, which means that the coloring of the parent of $v$ is incorrect. This contradicts our assumption that we know the correct color of the parent (note that we have assumed a valid coloring exists!)

So, we can now color the vertices by traversing the tree from root to leaves, again layer by layer: we check at each vertex $v$ whether it separates vertices of some color (as a valid coloring exists, this is at most once color) and fill in that color. If it separates no vertices of the same color, we simply give it an unused color from $[1,n]$.

Efficiency: Coloring the sub-tree requires traversing the tree from bottom to top. As we need to compute with the field $v.subcolors$ at most once for every edge in the tree, this part takes $O(|E|) = O(|V|) = O(n)$ time.

For the down-traversal, we must perform a comparison again for each edge. We can check for each color and vertex adjacent to $v$ whether it occurs and see if it is a separator if it occurs twice. This takes $O(\mathrm{degree}(v)\cdot |C|)$ time if we store the color sets in a hash-table, where $|C|=n$, the number of colors. As the average degree of a tree is constant, performing this operation on all vertices takes $O(n^2)$ time.

So, in total, the algorithm runs in $O(n^2)$ time. This turned out to be fast enough for the testcases given in the contest.

This time could maybe be improved by using an efficient union algorithm to check the separator more efficiently. (Union-find doesn't seem to do the trick, as the sets aren't disjoint)


Give a DFSA that accepts $L_1 = \{x : \#_{01}(x) \mod 3 = 0\}$ using as few states as possible Let $L_1$ be the language over alphabet $\{0, 1\}$ defined by $L_1 = \{x : \#_{01}(x) \mod 3 = 0\}$.

Using as few states as possible, give a DFSA that accepts $L_1$.

Also give an appropriate state invariant for your DFSA.

I have a regex for it and that is $1^*(00^*11^*00^*11^*00^*11^*)1^*$.

An example of accepted strings are: 100111010001. Example of a rejected string is 01010101, since |01010101| $= 4 \mod 3 = 1 \neq 0$.

How would I draw it? Also do I come up with state invariant first or draw the dfsa first? I drew the dfsa first right now

100111010001 - gets accepted. However 01010101 also gets accepted when it should be rejected. Not sure how to limit it to just mod 3

Edit:

I believe this works. (I cant use regexes in state invariants)

$q_0$: $x$ must contain only $1$'s

$q_1$: $x$ contains 1's before any 0's and ends with a 0

..

not sure how to write the state invariant for this case

Hint, a correct regular expression is $1^*(00^*11^*00^*11^*00^*11^*)^*0^*$.

There are 6 states, where $q_{0,1}$ is the initial state. Both $q_{0,1}$ and $q_{0,0}$ are accepting states.

$q_{0,1}$: the number of 01s is a multiple of 3 and it ends with 1. Or empty word.
$q_{0,0}$: the number of 01s is a multiple of 3 and it ends with 0.
$q_{1,1}$: the number of 01s is 1 plus a multiple of 3 and it ends with 1.
$q_{1,0}$: the number of 01s is 1 plus a multiple of 3 and it ends with 0.
$q_{2,1}$: the number of 01s is 2 plus a multiple of 3 and it ends with 1.
$q_{2,0}$: the number of 01s is 2 plus a multiple of 3 and it ends with 0.


number of edges in a graph I got a problem related to graph theory -

Consider an undirected graph ܩ where self-loops are not allowed. The vertex set of G is
{(i,j):1<=i,j <=12}. There is an edge between (a, b) and (c, d) if |a-c|<=1 and |b-d|<=1
The number of edges in this graph is

Answer is given as 506
but I am calculating it as 600, please see attachment.

I am unable to get why it is coming as 506 instead of 600.

Thanks

For a grid in the range of $[n_1,n_2]$, according to the problem statment, the number of edges is:

$$\#edges=\frac{8 \times (n_2-n_1+1)^2- 4\times 5-4\times3\times(n_2-n_1-1)}{2}$$

explanation:
suppose every node has a degree of 8, then sum of the degrees is $8\times(n_2-n_1+1)^2$; For each corner we included 5 extra edges that must be removed (the term $4\times5$) and for every other border node we considered 3 more edges (the term $4\times3\times(n_2-n_1-1)$).

The solution for your problem is:

$$\frac{8(12-1+1)^2-4(5)-4\times3\times(12-1-1)}{2}=\frac{8(144)-20-12(10)}{2}=\frac{1012}{2}=506$$


Minimum number of tree operations to normalize a labeled tree Given a binary tree with labels on the leaves, like $(bc)(ad)$ or $((af)e)(c(db))$, which we can interpret as a product of terms with respect to a commutative associative operation, how many applications of commutativity (swapping the two children of a node) and associativity (tree rotations) are needed to bring this tree to a sorted normal form like $a(b(cd))$ or $a(b(c(d(ef))))$? Examples:

$$(bc)(ad)\mapsto((bc)a)d\mapsto(a(bc))d\mapsto a((bc)d)\mapsto a(b(cd))$$

\begin{align}
&\phantom{{}\mapsto{}}((af)e)(c(db))\\
&\mapsto (a(fe))(c(db))\\
&\mapsto (a(fe))((cd)b)\\
&\mapsto (a(fe))(b(cd))\\
&\mapsto (a(ef))(b(cd))\\
&\mapsto a((ef)(b(cd)))\\
&\mapsto a((b(cd))(ef))\\
&\mapsto a(b((cd)(ef)))\\
&\mapsto a(b(c(d(ef))))
\end{align}

There are $C_{n-1}\cdot n!$ possible trees on $n$ elements, and about $2n$ possible operations to apply at each stage, so the information theoretic bound gives $\Omega(\log_{2n}(C_{n-1}\cdot n!))=\Omega(n)$. On the other hand, if we first fully right associate, then we can perform adjacent swaps with $O(1)$ operations, leading to an upper bound of $O(n^2)$ operations.

I suspect that $O(n\log n)$ operations suffice, perhaps even $O(n)$, but I have not been able to improve on the above bounds. I know that $O(n)$ operations work if it is possible to perform exchanges in $O(1)$, but every element has its depth change by at most 1 per operation, so exchanges are rather expensive ($O(n)$) in this model. Probably we want to keep the tree balanced during the sorting, but assuming a balanced tree it's not clear how to sort effectively by block swaps.

$O(n \log n)$ operations suffice, as you conjectured.  One can implement something akin to quicksort (using the median as the pivot in each stage).  I'll describe the details below.  For simplicity of exposition, let's assume $n$ is a power of two (though it all works for arbitrary powers of two).  We'll bring the tree into a normal form, which is a complete binary tree (i.e., all leaves are at the same depth, $\lg n$).

Let $\alpha$ be the $n/2$th label (in sorted order of the labels).  We'll first manipulate the tree so it has the form $xy$, where $x$ is a subtree of size $n/2$ containing all items $\le \alpha$ and $y$ is a subtree of size $n/2$ containing all items $>\alpha$.  Call this the partition operation.  Then, we'll recursively apply the algorithm to the left subtree and to the right subtree.

I'll argue below that the partition operation can be done with $O(n)$ operations.  Then it follows that the total number of operations performed by this algorithm obeys the recurrence relation

$$T(n) = 2 T(n/2) + O(n),$$

which has the solution $T(n) = O(n \log n)$. It follows that this algorithm takes $O(n \log n)$ operations.

So how do we do the partition operation?  Well, suppose the tree is originally of the form $uv$.  We'll recursively apply the partition algorithm to $u$, to get a tree of the form $u_0u_1$ where the leaves of $u_0u_1$ are the same as the leaves of $u$, but now $u_0$ has all items of $u$ that are $\le \alpha$ and $u_1$ has the items that are $>\alpha$.  Similarly, we'll recursively apply the partition algorithm to $v$, to get $v_0v_1$.  So after the recursive calls to the partition algorithm, the tree has the form $(u_0u_1)(v_0v_1)$.  Now by a constant number of applications of commutatively and associativity, this can be transformed to $(u_0v_0)(u_1v_1)$.  At this point, the tree has the desired form, as $u_0v_0$ is composed of all of the items of $uv$ that are $\le \alpha$ and $u_1v_1$ is composed of all of the items of $uv$ that are $>\alpha$.

The running time of the partition algorithm is given by the recurrence

$$U(n) = 2U(n/2) + O(1),$$

which has the solution $U(n) = O(n)$.  Thus, the partition algorithm can be done in $O(n)$ operations.


How to get the best factor for abstract algorithm that has expected cost?! 1.10 Let A be an algorithm for minimization NP-optimization problem such that the expected cost of the solution produced by A is at most $\alpha OPT$, for a constant $\alpha>1$. What is the best approximation guarantee you can establish for this problem using algorithm A?

Hint: A guarantee of $2\alpha-1$ follows easily.
to be honest, I don't really understand the question good. So usually when we want an approximation factor we take the ratio between solution of algorithm A and OPT of problem. could you explain the problem in other way! and how we get factor of $2\alpha-1$. Suppose I want to use Markov's bound, since the information we know is expected value. Thus, I would get $\alpha OPT/a$ for $a>0$. I don't see any logic here! I would like any help in terms of explanation!

Thank you!

I don't know what the author of the question means with "approximation guarantee" (is it defined earlier in the book?), so I am just going to tell you what you can derive from the information that's given.

If the expected value of the algorithm is $\mathbb{E}=v$, then the probability that the algorithm outputs a value larger than $kv$ is at most $\frac{1}{k}$, from Markov's bound, if the cost function never goes negative. So if you run the algorithm $t$ times, then the probability that the minimum value among all trials is greater than $kv$, is at most $k^{-t}$ (why? because the trials are independent).

There are no hard guarantees until there is more information.


Is Palindrome subset of a regular language regular? Suppose we have $L$ being a regular language with alphabet $\Sigma$, if we define $M=\{ x \in \Sigma^{*}  \mid xx^{R} \in L  \}$, then we know that $M$ contains all half copies of palindrome strings of $L$, now here comes the question, is $M$ regular?

Is it easy to see that when $L$ is finite, then $M$ is clearly also finite hence regular. However, what if $L$ is infinite? I think it will be non-regular and try to pumping lemma but does not work...

The subset of all palindromes in L is obviously not usually regular, take the simple example $a^*ba^*$ where the subset of palindromes $a^nba^n$ is not regular. But that is not the question. The question is about the set of all left halves of palindromes in L.

Assume you have an FSM for L (that is an FSM describing and defining L). You can take that FSM and use a simple algorithm to determine if w is in M:

Given a state S, define succ(S, a) as the state that the FSM will transition to from state S with input a, or nil if there is no transition for a. For a set of states T, define pred(T, a) as the set of states S such that succ(S, a) is not nil and an element of T.

To determine if w is in L, you would start with S = $S_0$. Then for every symbol s in w, you replace S with succ(S, s), exiting the loop if S is nil. Finally, w is in L if and only if S ≠ nil and S is an accepting state.

To determine if w is in M, you start with S = $S_0$ and T = set of accepting states. Then for every symbol s in w, you replace S with succ(S, s) and T with pred(T, s), exiting the loop if S is nil or T is empty. Finally, w is in M if and only if S ≠ nil and S is an element of T.

Instead of using this algorithm, you can quite easily construct an FSM for M.


Decidability of $SEQ_{CFG} = \{⟨G,H⟩ \mid \text{$G,H$ are CFGs and $L(G) ⊆ L(H)$}\}$ How can I prove that $SEQ_{CFG} = \{⟨G,H⟩ \mid \text{$G,H$ are CFGs and $L(G) ⊆ L(H)$}\}$ is decidable ?

I know that $EQ_{CFG} = \{⟨G, H⟩ \mid \text{$G,H$ are CFGs and $L(G) = L(H)$}\}$ is not.

We also know that $L(G)=L(H)$ iff both $L(G)\subseteq L(H)$ and $L(H)\subseteq L(G)$.

Now assume $SEQ_{CFG}$ is decidable, then we can decide both ...


A question on decidable formal languages and turing machines Let $L' \subseteq L \subseteq \Sigma^*$ be decidable languages with deterministic Turing machines $M'$ and $M$ which decide the languages. Typically we have $t_M(w) \le t_{M'}(w)$ for all $w \in \Sigma^*$, where $t_M(w)$ is the time of $M$ on input $w$.

Suppose furthermore that $M$ and $M'$ have minimum length when interpreted on some chosen universal Turing machine $U$.
So if $M''$ decides $L'$ then $l(M'')\ge l(M')$ where $l(M)$ is the length of $M$ when interpreted on $U$.

Is this just a coincidence of the chosen Turing machines, or does this property hold for all deciders of $L$ and $L'$ with minimum length?

"Typically" here means the following situation:

For instance if $L'$ is a decision problem on graphs and $L$ is the language of graphs (meaning that words correspond to adjacency matrix of a directed graph), then first for a word $w\in \Sigma^*$ one must decide if this word corresponds to an adjacency matrix of a graph, then decide if that graph has the property one is looking for. If you know a counterexample to that, that would also answer the question.

A counterexample is choosing L' as the empty language. That can be decided faster than most other languages.


Do I need to consider instance restrictions when showing a language is in P? I have already shown that 3-colorable for an unrestricted graph is in NP, but I was thinking about the similar language defined as the set of all acyclic $G$, where $G$ such that $G$ is 3-colorable. In my proposition of an algorithm in P, I wasn't sure if my algorithm needs to verify that $G$ indeed contains no cycle or if I assume all inputs are instances of this language (assume all inputs are acyclic graphs). In general, I was wondering if my algorithm has to decide whether the input is of the desired instance ON TOP OF actually showing the properties of the language can be done in polynomial time. I'm still learning so I am confused about this part and this has been bugging me for a while.

If this question is too confusing, consider 3SAT. Must I show that verifying the input is indeed a 3CNF is in P to conclude, or can I assume we are only considering inputs within an instance?

I was wondering if my algorithm has to decide whether the input is of the desired instance ON TOP OF actually showing the properties of the language can be done in polynomial time.

Very nice question!

What you are talking about is best characterized as promise problem, "a generalization of a decision problem where the input is promised to belong to a particular subset of all possible inputs". The conventional way to handle promise problem is there are no requirements on the output if the input does not belong to the promise. In particular, if you want to show a promise problem is in P of promise problems, your algorithm do not need to check whether the input is valid or not and your algorithm can behave arbitrarily if the input is invalid.

For an in-depth educational survey on promise problems, you are encouraged to read Oded Goldreich's exposition On Promise Problems, July 11, 2005.

However, if you want to show a promise problem is in P, your algorithm must check whether the input is valid or not and, if the input is invalid, a.k.a as a noninstance, output 0. Here P stands for the complexity class as in the famous P versus NP problem, a.k.a. P of decision problems, i.e. PTIME or DTIME$(n^{O(1)})$ as defined at Wikipedia, or the complexity class P as defined in section 34.1 Polynomial time of the popular textbook introduction to algorithm by CLRS, version 3.

Take 3SAT for an example. An algorithm that show 3SAT is in P (of decision problems) should check whether the input is a formula in conjunctive normal form each of whose clauses contains at most three literals among other restrictions. The algorithm should output 0 if it finds the input is not a valid instance of 3SAT.

It is easy to check whether a problem instance is a valid instance or not for almost all decision problems people have been interested in. It is so easy and so common that people have become so sloppy or efficient that this verification step is usually skipped or even forgotten in the specification of an algorithm. That might be the source of your confusion.

I would recommend beginners to write clearly this verification step for the first few occasions before joining the common practice.


Is the language of words that contain a square regular or context-free? $ L = \{w \in\{a,b\}^{*} : \exists_{x,y,z} ,   w=xyyz \wedge y \neq  \epsilon   \}$

I have a problem with this exercise. I need to determine if this language is regular, context-free or not both and prove. The word itself $ww$ above the alphabet $a, b$ is not context-free, but here we have $(a + b) ^ {*}$ before and after, and it changes a lot, I think.

Is it possible to describe this language with a regular expression? For example
$$(a + b) ^ {*} (aa + bb + abab + baba) (a + b) ^ {*}$$
So is the language regular?

A word is square-free if it contains no non-empty sub word of the form $y^2$. Your language consists of all words over $\{a,b\}$ which are not square-free. It is not difficult to enumerate (using exhaustive search) all square-free words over $\{a,b\}$:
$$
\epsilon, a, b, ab, ba, aba, bab.
$$
Since this list is finite, the language of square-free words over $\{a,b\}$ is trivially regular, and so is its complement.

In contrast, the language of square-free words over $\{a,b,c\}$ is not regular. This follows from the existence of an infinite square-free word $w$, which can be obtained from the Thue–Morse sequence.

Indeed, I claim that the set of prefixes of $w$ is pairwise inequivalent modulo your language. To see this, let $x,y$ be two such prefixes, say $x$ is a prefix of $y$. Then $y = xz$, and so $xz$ is square-free while $yz = xz^2$ isn’t.

Alternatively, we can apply the pumping lemma to the language of all square-free words over $\{a,b,c\}$. If the pumping length is $n$, take the prefix of $w$ of length $n$, and pump it up so that it contains a square. Similarly, since the Thue–Morse sequence is an infinite binary cube-free sequence, the language of cube-free words over $\{a,b\}$ is not regular.

The latter argument shows that the language of square-free words over $\{a,b,c\}$ and the language of cube-free words over $\{a,b\}$ are not context-free. This leaves the following questions open:

  Is the language of non-square-free words over $\{a,b,c\}$ context-free?
  Is the language of non-cube-free words over $\{a,b\}$ context-free?


Heuristic analysis of Bloom filters I am currently watching a lecture on Bloom filters, and the professor is doing a heuristic analysis of Bloom filters.

It's all based on the following assumption:

  All $h_{i}(x)$'s are uniformly random and independent (across different $i$'s and $x$'s)

Setup:

Bloom filter of length $n$ bits.
Data set $S$ is inserted into the Bloom filters.

The professors claims that for each bit of array $A$, the probability that it has been set to 1 is (under above assumption, and after data set has been inserted): $1 - (1 - 1/n)^{k|S|}$, where $k$ is the number of hash functions.

I am trying to understand why that's the probability.

He explains that as each of the $|S|$ objects gets inserted (0 or 1), there are $k$ "darts" thrown uniformly at random and independent from each other thrown into the array, so that gives me the intuition of why $k$ is being multiplied by $|S|$. He then says the probability that a given "dart" is one of the $n$ bits is $1/n$. Since there are a total of $k|S|$ "darts" thrown at the end, it makes sense that after the whole set $S$ has been inserted, the probability that a given bit has been hit is $(1/n)^{k|S|}$, and the probability that it hasn't been hit is $(1-1/n)^{k|S|}$. But I don't understand why all that is being subtracted from $1$ at the end to end up being $1 - (1 - 1/n)^{k|S|}$, so clearly I'm missing something...

Can somebody explain this to me?

A bit is set to 1 if it has been hit. It has $k|S|$ chances of being hit, and each time it is hit with probability $1/n$. Using a union bound, the probability that a bit is hit is at most $k|S|/n$.

We can improve on this bound by calculating instead the probability that a bit is 0, that is, that it is not hit. For a bit not to be hit, it has to be missed each time. Since it has $k|S|$ opportunities to be hit, and each time it is missed with probability $1-1/n$, in total a bit is missed with probability $(1-1/n)^{k|S|}$. Thus a bit is not missed with probability $1-(1-1/n)^{k|S|}$.


What precisely differentiates Computer Science from Mathematics in theoretical context? I am a university level student of Computer Science having a great passion to study Mathematics. I have a firm belief that Computer Science or Theoretical Computer Science is a direct branch of Mathematics and Logic and also of the opinion that a Computer Science degree has always to be Math oriented as a matter of fact. Please correct me if I am wrong.

I frankly feel that there isn't a lot of difference in the 2 subjects to be frank as every "computation" involves "calculation", although every "calculation" might not be a "computation". Again please provide substantial information and evidence and do update me if I am mistaken here. Thank you

Theoretical computer science is what theoretical computer scientists do; and mathematics is what mathematicians do. Other than that, there is no accepted definition of either. One might argue that theoretical computer science is a particular branch (or branches) of mathematics, influenced (at least originally) by the problem of efficient computation.

Many areas of mathematics are clearly not theoretical computer science, say functional analysis, category theory, algebraic geometry, algebraic number theory, and many others. However, sometimes these areas are applied to theoretical computer science. Parts of them might then form part of theoretical computer science, if there is a community of theoretical computer scientists who decided to work on them.

On the other hand, computability theory is not necessarily part of theoretical computer science, depending on which community of theoretical computer science one takes as reference. Theoretical computer science (or at least its part known as "Theory A") is traditionally about what can be efficiently computed rather than about what can be computed at all.

Many mathematical theorems have no computational content, and in some cases this can be made precise. One example is Kawamura's result that ODEs are hard to solve in general. It is not true that every mathematical proof has constructive content – indeed there are mathematical techniques which are inherently non-constructive, for example the use of compactness or the axiom of choice in any of its other guises.

If you are interested in the computational content of mathematical statements and proofs, you might want to look into reverse mathematics and bounded arithmetic (sometimes known as feasible mathematics or feasible arithmetic).


How to prove strict space lower bounds using crossing sequences in Turing machines? I understand the notion of crossing sequences when talking about time, however how are they used to actually prove strict lower bounds for some decision/search problems?

For example, suppose that you have an array of size N and you want to find the maximum number in it.

Speaking informally, we need at least a pointer to run through the input and some other variable to update whenever we find a number in the input tape that is bigger than the temporary number in our work tape, thus leading us to use Ω(logn) space.

However, how can you prove that you can't do it in O(1) space? Many articles online are using crossing sequences for proving space lower bounds, but they don't show how to do it, they just say something along the lines of "using crossing sequences it's trivial to show that the space lower bound is ..."

which isn't very helpful for beginners like me. Thanks!

A deterministic algorithm running in space $S$ runs in time $\exp S$. If you don't go over the entire array then you don't know the maximum number (formally speaking, consider two arrays differing in the last element, in only one of which it is the maximum). It takes time $n$ to go over the entire array. So $S = \Omega(\log n)$.


How an I prove if this language is decidable or not In the context of computability and turing machines

Let $L_1$ be an undecidable language and $L_2 = \{n \in \mathbb{N} | \exists x \in L_1  |x| \geq n\}$

How can I prove if $L_2$ is decidable or not?

I guess $L_2$ is not decidable in general and it depends on $L_1$ but still nothing proved. \

Consider two cases:

$L_1$ is finite, and so there is a word of maximal length.
$L_1$ is infinite, and so there are words of arbitrarily large length.

Try to see if you can decide $L_2$ in these two cases.


Why is a negative number a pseudo-positive number in ones' complement? I'm studying ones' complement representation and I read in a book that a negative number in ones' complement is a pseudo-positive of value $R^n - 1 - |x|$.

However there is no demostration and I can't find it anywhere. If someone could tell me the reason I will be very thankful.

You are asking two questions:

How can I prove that negative numbers are stored as pseudopositive?
Why are negative numbers stored as pseudopositive?

The answer to the first question is that no proof is needed, since one's complement is a way of representing signed numbers as unsigned numbers, and it specifies that negative numbers are stored in this specific way. There is nothing to prove here, just read the definition of one's complement. In other words, this is true by definition.

Regarding the second question, storing numbers in this way facilitates arithmetic. For example, to add two numbers, you just add them as unsigned numbers, with an extra little fiddling depending on the sign bits; in two's complement you don't even need the extra fiddling.


Space complexity for storing integers in Python So I was watching this mock interview by an Airbnb engineer on interviewing.io (https://youtu.be/cdCeU8DJvPM?t=1224) and around ~20:11 seconds he raises an interesting point.

The question that the interviewee was trying to solve was -

Array 1 has all unique integers.
Array 2 has the same integers as array 1, except one integer missing.
The code has to find that missing integer.

The interviewee suggested we can just subtract the sum of the second array from that of the first array and that'd give us the missing integer, and since these are just sums (integers), they'd take O(1) space. But the interviewer then said it's not actually constant since a sufficiently large sum can take more space than a smaller sum.

While that is true, and I double-checked it, via -

In [1]: import sys

In [2]: sys.getsizeof(90)
Out[2]: 24

In [3]: sys.getsizeof(9000000000000000000000000000000000)
Out[3]: 40

what complexity is it then?

Is saying constant space complexity for these algorithms wrong then?

It depends on the model of computation. In the transdichotomous model, which is the standard model in the analysis of algorithms, we assume that the word size is $w=O(\log n)$ bits, where $n$ is the size of input in bits. In this assumption, the sum of the input can be represented with 1 word, so the space complexity is $O(1)$ words. Measured in bits, the space complexity is $O(\log N + \log M)$, where $N$ is the number of integers in input and $M$ is maximum value in input. However note that normally we don't measure space complexity in bits: if we did, then the space complexity of most linear time algorithms, like DFS and BFS would have an extra $O(\log n)$ factor.

In my opinion, there is no single right answer when talking about space complexities like this in an informal setting like job interview. However you should keep in mind that having a single right answer is not the goal of job interviews.


Is it possible to create a CFG with succesive palindromes? In one of my homework I am requested to find a Context-free-grammar (CFG) and a push down automaton (PDA) for the following language:

$L = \{x_1\#x_2\#...\#x_k | k \geq 2, \text{ each } x_i \in \{a, b\}^*, \text{ and for some } i \text{ and } j, x_i=x_j^\mathcal{R}\}$

My problem is that the statement

$\text{ ... and for some } i \text{ and } j, x_i=x_j^\mathcal{R}\}$,

i.e. any two pairs in the sequence must be each others reverses, forces us to make all $x_i$'s palindromes, as that is the only way any two are guaranteed reverses of each other.

If that interpretation is correct, I think the problem is impossible to solve with a Context free grammar, or not? This leads me to believe I interpreted the statement wrong and it means something else, but I can't figure out what.

A reference to $j$ is missing. My guess is that it should read $x_i=x_j^{\mathcal R}$. This means that some pair $x_i$, $x_j$ should be each others reverse, or one string should be a palindrome. This can be done with a CFG.

(after correction)
It does not say that for each $i$ there should be a $j$, it just states that some $i,j$ exist. One pair will do.  If the word "any" would have been used then this would probably change the meaning, although "any" sometimes is ambiguous.


Greedy choice and matroids (greedoids) As I was going through the material about the greedy approach, I came to know that a knowledge on matroids (greedoids) will help me approaching the problem properly. After reading about matroids I have roughly understood what matroids are. But how do you use the concept of a matroid for solving a given optimisation problem?

Take, for example, the activity selection problem. What are the steps to use matroid theory for solving the problem?

The connection is that if a you can represent the structure underlying your optimisation problem as matroid, you can use the canonical greedy algorithm to optimise the sum of any positive weight function. If your optimisation goal fits this paradigm, you can solve your problem with the greedy approach.

Example

Consider the minimum spanning tree problem with positive edge weights¹. We will show that there is a matroid corresponding to that problem, implying that it can be solved greedily, that is by the canonical greedy algorithm on said matroid.

Let $G = (V,E,c)$ be an undirected graph with $c : E \to \mathbb{R}_+$ the edge-cost function. Then, $(E,I)$ with

$\qquad \displaystyle I = \{F \subseteq E \mid (V|_F, F) \text{ is a forest}\}$²

is a matroid. Thus, we can find the element of $I$ maximising the sum of edge weights $c'(e) = (\max_{e \in E}c(e)) - c(e)$. This happens to be a minimum spanning tree. Note that the canonical greedy algorithm is called Kruskal's algorithm in this context for historical reasons.

Proofs

To show: $(E,I)$ is a matroid. We have to verify three properties:

$\emptyset \in I$ -- the empty graph is a forest.
If $F \in I$, every subset of $F$ is in $I$ -- given an arbitrary forest, removing edges can not introduce cycles. Therefore, every subgraph of a forest is a forest.
For every $F_1,F_2 \in I$, $|F_1| > |F_2|$ implies that there is $e \in F_1 \setminus F_2$ so that $F_2 \cup \{e\} \in I$ -- consider an arbitrary forest $F_1$ and a smaller one $F_2$. Assume there is no such $e$. That means that all edges in $F_1$ lie in cuts induced by edges in $F_2$³. As there are only $|F_2|$ such cuts, at least one pair of edges in $F_1$ shares a cut; this contradicts that $F_1$ is a forest.

To show: any element $F^*$ with maximum weight in $I$ is a minimum spanning tree of $G$. First of all, it is clear $F^*$ has maximum weight according to $c'$, so by definition of $c'$, it also has minimum weight according to $c$. Now all we have to show is that it is a spanning tree: if it was not, it would not be maximal in the sense that we could still add edges (with positive weight), contradicting maximum weight.

We can deal with negative edge weights by adding the minimum weight plus one to all weights.
A forest is a disjoint union of trees.
A graph contains a cycle if and only if there is a cut with more than one edge.


$\epsilon$ - Nash Equilibrium exceeds Nash Equilibrium I wonder if there exists a game in which $\epsilon$ - Nash equilibrium leads to a much higher payoff than any other Nash equilibrium.

Show, for every $\epsilon$ > 0, a two player game where there is an $\epsilon$-Nash equilibrium in which  both players have a much higher payoff then in any Nash equilibrium.

What is $\epsilon$ Nash - equilibrium.$\sigma$ is $\epsilon$-Nash equilibrium, if $ u_i(\sigma) \geq u_i(\sigma_i, \sigma_{-i}) - \epsilon, \forall \sigma_i \in \Delta(S_i), \forall i \in N$.

It sounds very counter-intuitive, in other word I have to show the game where $\epsilon$ - Nash equilibrium, which is according to the definition not the best strategy to play indeed leads to the best payoff.

Could you give such en example?

It is quite simple: if you enlarge the set of possibilities you can get better values.

Here, in place of requiring the possibilities to be equilibrium we require them to be almost equilibrium, a larger set of possibilities, therefore a higher possible value.

Here is a simple example:

$$\left[\begin{array}{cc}
5/5 & 0/6 \\
6/0 & 1/1 \\
\end{array}\right]$$

Let $\epsilon = 2$. Now $5/5$ on the top left corner is an $\epsilon$-equilibrium where as the equilibrium is $1/1$.


Please explain linear programming as seen for this load balancing problem I have at hand a linear program related to load balancing. However I have no idea what this is and wikipedia gives me something too simplified/abstract to be useful.

I wonder if someone can explain the basic lingo used in the formulation of the linear program. The goal of the program is of course to introduce the maximum amount of load capable on the lightest loaded machine.

Let

$p_i$ be load of processor $i$
$L$ be our load to be distributed
$x_i$ be the fraction of load $L$ distributed to processor $i$
$\gamma$ be the minimum of final load after distribution of $L$

Then solve:

$$max_{x,\gamma} \gamma$$

subject to $\gamma \underline 1 \leq p + xL$, $\underline 1'x = 1, x \geq 0$, $\underline 1$ is the one vector

Some confusions:

How do you physically characterize the load of a processor, is it
equivalent to CPU utilization? i.e. what can I do to find out what
the load of my processor is currently having
How is the fraction of load $L$ to be distributed determined?
If $\gamma$ is the minimum final load after L, then why do we
maximize it? wouldn't that be equivalent to maximize the left over
work to be done?

How do you physically characterize the load of a processor, is it equivalent to CPU utilization?

The program is modelling load like this. Whether you feel it's a good way to model load, and whether you can think of any real version of load that works like this is a separate issue.

You are running a storage facility for water. The key "facts" about water are:

It's just water and all water is the same. If I ask you to store a litre of water for me and I come back for it a week later, I don't care if you give me back exactly the same molecules of water: I just want you to give me a litre of water. (Economists call a substance with this property "fungible".)
Water is infinitely subdivisible. If I give you a litre of water, you can split it into any number of smaller quantities, without restriction. (Atoms? Shmatoms!)

OK. In your water storage facility, you have $n$ tanks, each of which can hold an unbounded amount of water (you were sure you only needed one such tank, but the TankCorp salesman was very persuasive). At any particular time, the $i$th tank contains $p_i$ litres of water.  A new customer has just arrived with $L$ litres and you need to decide if you can store that and, if so, what is the best way of doing that.

You'll put $x_i$ litres of water in each of your tanks.  You can choose the value of each $x_i$ however you want but, if you accept the customer, you must store all of his water, which means you must have $\sum_i x_i = L$. Also, TankCorp tanks do occasionally burst so you want to fill the tanks as evenly as possible so that, if a tank does burst, you know it won't be a super-full one: you want the loads in the tanks to be balanced.  This is achieved by making the emptiest tank as full as possible.  Why? Because the total amount of water in all the tanks is fixed so, if one tank has less water in it, you can always make the quantities more equal by taking water from a very full tank and transfering it to the emptiest one.

Your job is to pick values for the $x_i$ to satisfy these constraints. Note that if, at the start of the day, each of your tanks is empty, then the solution is trivial: you just set $x_i = L/n$ for each $i$ and each tank contains the same amount of water.

OK, that's the model.  You can use it to represent any kind of load that resembles the idealized water I described: it must be arbitrarily subdivisible (you can split it between your servers however you want) and fungible (your client don't care which server does any fraction of the work). Literally speaking, that's nothing at all, but we can get a good approximation if we replace "infinitely subdivisible" by "subdivisible a lot".  For example, suppose you're running a web server cluster.  You can't literally divide a burst of a thousand requests between the machines in your cluster in any fraction ("I'll do 4.7 requests on server 1, ...") you want but you can divide it into any number of thousandths, which is close enough.

  i.e. what can I do to find out what the load of my processor is currently having?

I'm not sure what you mean.  This isn't a system for measuring load, it's a system for assigning fractions of jobs to servers so that each server will have about the same load.

  How is the fraction of load $L$ to be distributed determined?

By solving the program!  (I.e., choosing values for the $x_i$ that satisfy the constraints.)

  If $\gamma$ is the minimum final load after $L$, then why do we maximize it? Wouldn't that be equivalent to maximize the left over work to be done?

No, because the total work to be done is fixed. Maximizing the least-busy server means that there's less work for the busiest server to do, so you finish as soon as possible.


Good characterization of unsatisfiable Horn3SAT formula? Horn3SAT is $P$-complete problem under logspace reductions. Since Horn3SAT is in $P$ its complement must have short witnesses. I am looking for natural short proof that a Horn3SAT formula is not satisfiable. Examples for similar problems in $P$ are 2-coloring problem and planarity problem. A graph is not 2-colorable if and only if it contains an odd cycle. A graph is not planar if and only if it contains a subgraph that is a subdivision of $K_5$ or $K_{3,3}$.

  Is there a good characterization of Horn3SAT formulas that are not satisfiable? What does constitute a natural short witness for unsatisfiable Horn3SAT formulas?

I am not interested in algorithmic proof such as running an algorithm for deciding Horn3SAT problem. I am only interested in good characterizations similar in spirit to the above two examples.

EDIT: As illustrated by the two examples above, I am only interested in characterizations of the complement set of Horn3SAT in terms of some forbidden structure.

You should not expect a proof that is asymptotically shorter than the formula itself.  For instance, consider

$$(x_1 \implies x_2) \land (x_2 \implies x_3) \land \dots \land (x_{n-1} \implies x_n) \land x_1 \land \neg x_n.$$

This formula is not satisfiable, but any proof of unsatisfiability will need to have size $\Omega(n)$.

If you're willing to accept a "proof" of size $n$, then the formula itself arguably qualifies as a proof (as it's easy to check that a given formula is not satisfiable).

Alternatively, any chain of deductions that ends in a contradiction qualifies as a proof, where each step in the chain is a variable and its inferred truth value, as justified by a clause in the Horn3SAT formula and previously inferred variable truth values.  If the formula is not satisfiable, then there must exist such a chain of deductions of size $O(n)$.  The chain of deductions is easily verifiable and thus constitutes a proof of unsatisfiability.  In other words, we derive a directed implication graph from the input Horn3SAT formula; the proof of unsatisfiability is then a directed path in the graph from some $x_i$ to $\neg x_i$.

If none of these meets your needs, you'll need to define what you're looking for more carefully.