What does it mean to be Turing reducible? I'm confused about what it means to be Turing reducible. I thought I understood what it meant, but apparently not.

$A \leq B $ Means that A is Turing reducible to B. This means that given an oracle for Machine B, A can be solved.

I'm confused in the case of SUPERHALT which decides whether a Turing machine with access to the HALT oracle halts or not. I feel like SUPERHALT is reducible to HALT because I can just put any Turing machine into a HALT oracle and then put that result into another HALT oracle.

So in summary I believe:

Given a Turing machine M and input x $\epsilon \{1,0\}^*$ and oracle $HALT$, $$SUPERHALT(M(x)) <_T HALT(M(x))$$ because $$SUPERHALT(M(x)) = HALT(HALT(<M(x)>)$$
Which is wrong, but I just want to know what I'm misunderstanding.

From wikipedia article Turing Reduction, in computability theory, a Turing reduction from a problem $A$ to a problem $B$, is a reduction which solves $A$, assuming the solution to $B$ is already known (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to solve $A$ if it had available to it a subroutine for solving $B$. More formally, a Turing reduction is a function computable by an oracle machine with an oracle for $B$. Turing reductions can be applied to both decision problems and function problems.

This potentially allows us, along with a few other things, to solve problem $A$ using a deterministic Turing machine if $B$ is solvable using deterministic Turing machine.

I assume $SUPERHALT = \{ \langle M,x \rangle \ | \ M^{HALT}$ halts on input $x \}$. If so, then your reduction is incorrect.

First of all, a Turing machine $M$, that uses $HALT$ as an oracle, cannot be used as a non-oracle machine and given as an input of $HALT$. So using something like $HALT(\langle M, x \rangle)$ leads nowhere.

We can use relativizing proof to prove that $SUPERHALT$ is unsolvable even with availability of $HALT$ as an oracle.
We simply take Turing's original proof (with the machine given as self-input) that the halting problem is unsolvable, and give all the machines an oracle for the halting problem. Everything in the proof goes through as before.

From the fact that $SUPERHALT$ is unsolvable (even with the availability of $HALT$ as an oracle) we can prove $SUPERHALT \not\leq_T HALT$. Suppose there is a turing reduction $M'$ for $SUPERHALT$, which uses $HALT$ as a subroutine. Then this $M'$ which  uses $HALT$ as an oracle is able to decide  $\langle M^{HALT},x\rangle \in SUPERHALT$.   This is a contradiction. Hence $SUPERHALT \not\leq_T HALT$.


Lower bound for Convex hull By making use of the fact that sorting $n$ numbers requires
$\Omega(n \log n)$ steps for any optimal algorithm (which uses 'comparison' for sorting), how can I prove that finding the convex-hull of $n$ points is bounded by $\Omega (n \log n)$ steps?

If you could create the convex-hull in $o(n \log n)$ time, this would imply, that you can sort $n$ numbers in $o(n\log n)$ time.

You do this with contradiction. You have $n$ numbers $(x_1, x_2, \ldots, x_n)$, which you would like to sort. From these numbers, you create points $P$ in 2D space in some fashion. For example $p_i=(x_i,x_i^2)$.

On these newly constructed points $P$ you call the algorithm for convex hull, which returns you the actual convex hull.

After that, you simultaneously traverse upper and lower hull, from the lower left-most point in (which you find in $O(n)$ time), to the upper right-most point. With this traversal you actually sort the numbers. Let $p_i$ and $p_j$ be the next points on lower and upper hull, then if $x_i<x_j$, you move one step ahead on the lower hull and add $x_i$ to the end of the sorted array (else you take one step ahead on the upper hull and add $x_j$ to the array). You then finish when the traversals meet in the upper right-most point of the convex hull.

The algorithm that I described is run in $O(n)$ time. So if the convex-hull algorithm would be $o(n\log n)$, the sorting of $n$ numbers could be also done in $o(n\log n)$ time, which is a contradiction since we know that sorting $n$ numbers takes at least $\Omega(n \log n)$ time.


Converting a NFA to its equivalent regular expression I'm new to regular expressions and I'm currently working on some exercises on converting DFA's and NFA's into their equivalent regular expressions.

I have the following NFA:

I'm using the state elimination method to obtain the regular expression for the NFA. So I first introduced two new states, $q_{start}$ (the new start state of the NFA) and $q_{end}$ (the new and only accepting state of the NFA).
After that, I eliminated the states one after the other.

To eliminate the states, I pick a state $p_e$ to be eliminated. Then for every pair $(p_1,p_2)$ with $p_1, p_2 \neq p_e$ and transitions from $p_1$ to $p_e$ and from $p_e$ to $p_2$, I determine the labels $r_0,r_1,r_2,r_3$ of this general automaton

wipe out $p_e$ and replace $(p_1,r_0,p_2)$ with $(p_1,r_0+r_1 r^{*}_2r_3,p_2)$.

I already eliminated states $q_0$ and $q_1$, but I have no idea how to eliminate state $q_4$, since it has no outgoing transitions except to itself. Could you please help me out with that?

Technically it can be reduced, by introducing a regular expression for the empty set, which represents the missing edge.

However, $q_4$ is completely useless for the language. They can be dropped without changing the accepted language. That should save some work.


I know the algorithms, but i still don't know how to approach the questions I study Graphs Analysis by myself and i understood most of the material just fine. But, there is one huge problem with my approach that prevents me from solving tests. I don't know how to build new Graphs based on requirements and i'll give an examples:

Question: G = (V,E) is a directed graph with no cycles (DAG) and w: E->R for each edge. There is an efficient algorithm that in given vertices s and t in the graph it finds the minimum weight path contains with at least 3 edges.
So far it great - i understand the question just fine.

Step 1:  For each vertex v in V, we mark:
v1 = (v, 1), v1 = (v, 2), v3 = (v, 3), v4 = (v, 4)

Given G = (V, E), we'll build new graph G'=(V',E') where:
V'={v1, v2, v3, v4| for each v in V}

E' = {(v1, u2), (v2, u3), ____(1)____}

for each (ui, vj) in E', w(e) = {w(u, v)| (u, v) in E and (ui, vj) in E'}

(1) = ?

a. (v3, u4), (v4, u4) - the correct answer

b. (v3, u3)

c. (v3, u4),(v4, u3)

d. (v3, u4)

step 2: Apply DAG algorithm from s1.

step 3: return the weight of the path from s1 to t4.

I know how DAG works, but i don't know how to build the new graph in order to see it, how do i build the new graph?

i don't need to know what to do in every situation, i just don't know how to deal with it and build a new graph according the demands. The steps are derived from the question itself, but i didn't get the first step in the creation of the new graph. Why there is a need to create a new graph at all?

Allright, if I read this correctly here is what I think it should do (Some parts are possibly missing or badly formatted, but the following should make sense):

You basically copy your graph 4 times into different layers. Let's call them L1,L2,L3,L4

In L1, the highest Layer, every connection from the original graph instead goes down to L2.

From L2 every connection goes to L3, and from L3 to L4

Finally L4 looks like your original graph.

So if you search for the shortest path between u and v with at least three edges, you start at u in L1 and want to end at v in L4

Since you can only move down 1 layer at a time, you need at least three edges to reach v.

Take this graph as an example:

Let's assume we want to move from the left to the right, and the upper connection is the

shortest one. Then the correct answer is still to move through every other node, because taking the shortcut uses too few edges.

If we convert this graph we obtain the following:

Here we want to reach the bottom right from the top left. As you can see, finding a solution in this graph, automatically gives us a solution with at least three edges.

Note: Sorry that the vertices are not labelled, could not figure out the text function in the drawing tool I used :/


Chromatic polynomial of a cycle - Interpreting its terms I am learning about graph coloring. One of the exercise problems(grimaldi) led me to derive the chromatic polynomial for any cycle($C_n, n \ge 3$).

$P(C_n, \lambda) = (\lambda - 1)^n + (-1)^n(\lambda - 1)$, where $\lambda$ is the number of colours available

Is it possible to interpret the terms of above polynomial? I need help doing the same.

There is a theorem of Whitney answering your question. Let
$$ P(G,\lambda) = \sum_{k=0}^n (-1)^k a_k \lambda^{n-k}. $$
Then $a_k$ is the number of $k$-subsets of the edges of $G$ not containing any broken cycle. A broken cycle of $G$ is obtained from a cycle of $G$ by removing its maximum edge according to some fixed ordering of the edges.

For example, if $G = C_n$ then for $k < n-1$, $a_k = \binom{n}{k}$, and $a_{n-1} = \binom{n}{n-1} - 1$, since we miss one broken cycle.

For a proof and references to other proofs, see this paper.


Proving DPATH is NP-complete by a reduction from HAMPATH I have a language DPATH that I'm trying to complete is NP-complete.

DPATH = {<G, a1,...,an>|G is a digraph with a directed path that covers the sequence
a1,...,an}

All of the nodes in the sequence has to be visited exactly one time, but it doesn't matter in which order they are visited.

I am trying to show a reduction from HAMPATH to DPATH but I'm having some difficulties. When given input <G, s, t> I have to create a computable function f, that outputs <G, a1,...,an>. Can i say that a1 = s, and an = t, and that each node that the hamiltonian path goes through is labeled with a node from the sequence? My problem with this, is that what if the HAMPATH graph has more nodes than the sequence? Do I have to take this into account when creating the reduction?

Remember that given the HAMPATH instance, you are constructing the DPATH instance. As long as

it's a valid instance of DPATH,
it's a Yes-instance if and only if the HAMPATH instance is, and
it's computable in polynomial time,

you can do whatever you want. So in particular, you get to pick how long the sequence is, you can pick any $a_{i}$ to be $s$ or $t$ (though in this case you may want to think carefully how you ensure that these are the first and last vertices in the path - otherwise it might be hard to argue for the Hamiltonian path), you don't even have to have the graph $G$ in the HAMPATH instance be the graph $G'$ in the DPATH instance (I suggest that you look at something very close to it though).

In the spoiler below are some additional hints, but don't use them unless you're really stuck - you learn a lot less if you don't put in the effort and time.

   One thing you have to do is take the HAMPATH graph and make it directed. There is a very simple way to turn undirected graphs into directed graphs, and it can work here. Another is ensuring that $s$ is the start of the sequence and $t$ is the end. I suggest adding new vertices to be $a_{1}$ and $a_{n}$ such that you can only get out of $a_{1}$ and only get into $a_{n}$, but you still have to work out how to connect them into the graph - remember that you don't know whether $G$ has a Hamiltonian path, or where it is even if it does, so you have to take care of all possibilities.


Efficiently shuffling items in $N$ buckets using $O(N)$ space I’ve run into a challenging algorithm puzzle while trying to generate a large amount of test data. The problem is as follows:

We have $N$ buckets, $B_1$ through $B_N$. Each bucket $B_i$ maps to a unique item $a_i$ and a count $k_i$. Altogether, the collection holds $T=\sum_1^N{k_i}$ items. This is a more compact representation of a vector of $T$ items where each $a_i$ is repeated $k_i$ times.
We want to output a shuffled list of the $T$ items, all permutations equally probable, using only $O(N)$ space and minimal time complexity. (Assume a perfect RNG.)
$N$ is fairly large and $T$ is much larger; 5,000 and 5,000,000 in the problem that led me to this investigation.

(EDIT: further research instigated by @YuvalFilmus’s comment shows that this is equivalent to weighted sampling without replacement, a search term that leads to quite a lot of research.)

Now clearly the time complexity is at least $O(T)$ since we have to output that many items. But how closely can we approach that lower bound? Some algorithms:

Algorithm 1: Expand the buckets into a vector of $T$ items and use Fisher-Yates. This uses $O(T)$ time, but also $O(T)$ space, which we want to avoid.
Algorithm 2: For each step, choose a random number $R$ from $[0,T-1]$. Traverse the buckets, subtracting $k_i$ from $R$ each time, until $R<0$; then output $i$ and decrement $k_i$ and $T$. This seems correct and does not use extra space. However, it takes $O(NT)$ time, which is quite slow when $N$ is large.
Algorithm 3: Convert the vector of buckets into a balanced binary tree with buckets at the leaf nodes; the depth should be close to $\log_2{N}$. Each node stores the total count of all the buckets under it. To shuffle, choose a random number $R$ from $[0,T-1]$, then descend into the tree accordingly, decrementing each node count as we go; when descending to the right, reduce $R$ by the left count. When we reach a leaf node, output its value. It uses $O(N)$ space and $O(T\log{N})$ time.
Algorithm 3a: Same as Algorithm 3, but with a Huffman tree; this should be faster if the $k_i$ values vary widely, since the most often visited nodes will be closer to the root. The performance is more difficult to assess, but looks like it would vary from $O(T)$ to $O(T\log{N})$ depending on the distribution of $k_i$.

Algorithm 3 is the best I’ve come up with. Here are some illustrations to clarify it:

Does anyone know of a more efficient algorithm? I tried searching with various terms but could not find any discussion of this particular task.

Step 1. Store the buckets cumulatively. E.g. instead of storing $[3, 5, 2, 2]$ you store $[3, 8, 10, 12]$. This allows you to find using binary search in $\log n$ time what bucket the $k$th (out of $T$) item belongs to (and by extension which $a_i$ to output).

Step 2. Use a memory-less permutation of the range $[1, T]$. I personally like Sometimes-Recurse Shuffle. A memory-less permutation can give you $\pi(k)$ directly for arbitrary $k$ in $\log T$ time. Some example code I have written a couple years back show how simple it is (with toy PRF implementation - replace that): https://gist.github.com/orlp/33535eefce782a59e185e4a971cda1a3.

Step 3. To actually shuffle simply enumerate $k = 1, 2, \dots$, compute $\pi(k)$ using the memory-less permutation, and find which bucket $\pi(k)$ belongs to output the proper $a_i$. Total time complexity is $\log(T)$ per item, or $T \log(T)$ for the whole permutation.

The advantage is that you don't have to compute the whole permutation, you can also just directly compute the $k$th element in the permutation.


Heaps and Heapsort - Find the 7'th biggest value in a min heap by $O(1)$ I have a min heap.

I need to find the 7'th biggest value in the heap with $O(1)$.

I need to build the algorithm.

I dont realy have an idea how to get to this efficiency.

Help?

Thanks.

O(1) means: You need to do this with a fixed number of operations. Basically, write code without a loop. That's not difficult. It's a lot of code, but a fixed amount of code.

Look at your heap as if it was a binary tree. You want the 7th largest item in your tree. That's the sixth largest of the subtrees L and R. If the item at L is smaller than the item at R, it's the fifth largest item in the subtrees L, RL and RR, otherwise the fifth largest item in the subtrees R, LL and LR. And so on..


Algorithm for commonalities across related objects I am making early forays into the application of algorithms to best solve a problem and I am finding it difficult to choose the best application.

The problem is give the data below (two columns) find those ids where the linkedId matches entirely:

Input

id  linkedId
1   103
2   107
1   107
2   103
4   64
6   120
7   107
8   180
7   64
9   129

Expected output
[1,2] as the linkedIds match entirely for the two ids

As I look at the data, I would envisage a graph of some description so that I can establish the various links between the ids and linkedIds but I am at a loss as to how to approach this.

I do not want a solution but more guiding in the right direction.

Thanks

I came up with the idea of hashing when I just started looking at this, but seems that the range of the input data is not given, so it's very hard to decide on a specific algorithm.

However, there's another idea:

During input, create a table for each id, record all the linkedId of it, and the sum of linkedIds of it.
After recording all the input, you have tons of ways to find those ids whose sum of all linkedIds are the same, put them into groups, like an $O(n^2)$ brute-force or some $O(n\log(n))$ discretization. This step is a kind of classification, all ids in a group may not be the equivalent, but equivalent ids must be in the same group
Traverse through all groups, find those equivalent ids

This is expected to be a lot more efficient than brute-force. Hope it can help you.


How to generate a binary string so to minimize weighted bitwise distance? I've got an array of weights, for example

[1, 0, 3, 5]

The distance between two strings is defined as a sum of weights for different bits, like this:

size_t distance(const std::string& str1, const std::string& str2, const std::vector<size_t>& weights) {
  size_t result = 0;
  for (size_t i = 0; i < str1.size(); ++i) {
    if (str1[i] != str2.at(i))
      result += weights.at(i);
  }
  return result;
}

and starting string for example

'1101'

I need to generate strings in the way that strings with lowest distance from the original one go first, like this:

'1001'  # changed bits: 2nd. Because it has lowest weight. Distance is 0
'0101'  # changed bits: 1st.                               Distance is 1
'0001'  # changed bits: 1st, 2nd.                          Distance is 1
'1011'  # changed bits: 2nd, 3rd.                          Distance is 3
'1111'  # changed bits: 3rd.                               Distance is 3
'0111'  # changed bits: 1st, 3rd.                          Distance is 4
'0011'  # changed bits: 1st, 2nd, 3rd.                     Distance is 4
'1100'  # changed bits: 4th.                               Distance is 5
'1000'  # changed bits: 2nd, 4th.                          Distance is 5
'0100'  # changed bits: 1st, 4th.                          Distance is 6
'0000'  # changed bits: 1st, 2nd, 4th.                     Distance is 6
'1110'  # changed bits: 3rd, 4th.                          Distance is 8
'1010'  # changed bits: 2nd, 3rd, 4th.                     Distance is 8
'0110'  # changed bits: 1st, 3nd, 4th.                     Distance is 9
'0010'  # changed bits: 1st, 2nd, 3rd, 4th.                Distance is 9

I don't need code, I need just an algorithm which gets string of length N, array of weights of the same length and i as input and generates i-th combination, without generating the whole list and sorting it.

It is not possible to uniquely determine $i$-th combination because a function $f: \{0,1\}^* \to \mathbb{R}$ assigning distance to a string is not generally injective., that is - there may be multiple strings that correspond to a specific distance $d \in \mathbb{R}$ (which you example actually presents).

Also, it is not possible to know in advance all the possible distances as to determine which strings could be in $i$-th position, without actually calculating all the distances. It would be like knowing the shortest route to some destination by examining just that route.

I would suggest a different approach (but it will not make you happy as I generally think there is no way to achieve this in its fullest without generating all combinations); creating an algorithm that takes as input not $i$, but the distance $d$ and returns strings that are $d$ distance from your base string (note that it is in fact irrelevant).
You can then eliminate from further process the weights that are larger than $d$ (and even ones equal to $d$, with further care).

If you want all strings $d$ distance away and remaining weights vector is not too long, you can generate all subsets (a power set) of weights array and checking which has the sum $d$, but considering your restrictions on the solution - you do not want that because it would generate all the binary strings in the process.
If you need just one string on distance $d$, no matter which, you can implement some backtracking search/sum on the weights array to find a combination that sums to $d$. (You can then store ones you got and repeat this process ignoring ones you found already, if you still want all.)
You can model your problem as finding a path of length $d$ in a fully connected directed graph where you graph has $N$ nodes and the weight of an edge going to node $i$ is $weights[i]$. Then you can maybe use some optimized graph path finding (heuristic) algorithms, but that seems like an overkill.

I am quite sure this problem is in NP.


insert and delete in order statistic tree I am having trouble in understanding order-statistics tree .

Definition :
Every node in tree stores the number of descendants of itself .
Can you please explain the Algorithm or pseudocode how to Insert and Delete a node in the tree when tree is to be balanced .

Basically i want to find the rank of an element in the tree in O(log N) time complexity and nodes can be inserted and deleted in between querries .

P.S. I am able to understand the rank(x) operation .

The exact implementation of Insert and Delete depends on the underlying binary tree structure which is used, but the idea is that you maintain the size field throughout the operation. Consider for example the following Insert procedure, which always inserts its element as a new leaf:

Insert(Tree, $x$)

If Tree is empty, set Tree to be $x$, and return.
Let $r$ be the root of Tree, and Left, Right its children.
If $x < r$ then call Insert(Left, $x$), otherwise call Insert(Right, $x$).

Here is the updated algorithm, which maintains the size information:

Insert(Tree, $x$)

If Tree is empty, set Tree to be $x$ and size(Tree)=1, and return.
Increase size(Tree) by 1.
Let $r$ be the root of Tree, and Left, Right its children.
If $x < r$ then call Insert(Left, $x$), otherwise call Insert(Right, $x$).

This is the basic idea. You can take it from here.


Find small superset of at least k of n given sets Say we're given $n$ sets and the size of their union is $m$. We would like to construct a small set which contains at least $k$ of the $n$ given sets.

Lets assume that $m$ is less than some polynomial in $n$, i.e.: $m < P(n)$. In this case is there an efficient (polynomial) algorithm for the optimization problem:

Find the smallest set which contains at least $k$ of the $n$ given sets.

The problem is NP-complete. Here is a reduction from 3SAT-5, an NP-complete version of 3SAT in which every variable appears exactly 5 times (and so the number of variables and number of clauses are linearly related).

We start by constructing two set systems. The first system $\mathcal{S}$ consists of 6 sets $A_0,A_1,B_0,B_1,C_0,C_1$ and 15 elements $D = \{0,1\}^4 \setminus (1,1,1,1)$, and has the following property:
$$ |A_i \cup B_j \cup C_k| = \begin{cases} 14 & \text{if } i=j=k=0, \\ 13 & \text{otherwise}. \end{cases} $$
The set system is given by
$$\begin{align*}
A_i &= \{(a,b,c,d) \in D : a = i\}, \\
B_i &= \{(a,b,c,d) \in D : b = i\}, \\
C_i &= \{(a,b,c,d) \in D : c = i\}.
\end{align*}$$
The only elements not covered by $A_i \cup B_j \cup C_k$ are those of the form $(1-i,1-j,1-k,d)$. If $i = j = k = 0$ then there is one such element, otherwise there are two.

The second system $\mathcal{T}$ consists of $2n$ sets $X_1,Y_1,\ldots,X_n,Y_n$ and $O(n^2)$ elements, and has the following property. Call a family of $n$ sets out of $\mathcal{T}$ proper if it contains exactly one of each $X_i,Y_i$. All proper families of $n$ sets cover the same number of elements $M$, and each improper family of $n$ sets covers at least $M+1$ elements.

The set of elements consists of all unordered pairs of sets $\{S,T\}$ other than those of the form $\{X_i,Y_i\}$. Each set $S \in \mathcal{T}$ consists of all $2n-2$ pairs containing it. Let $\mathcal{F}$ be a family of $n$ sets, with complement $\overline{\mathcal{F}}$. The only elements not covered by $\mathcal{F}$ are those of the form $\{S,T\}$ where $S,T \in \overline{\mathcal{F}}$. If $\mathcal{F}$ is proper then so is $\overline{\mathcal{F}}$, and so there are $\binom{n}{2}$ elements not covered. If $\mathcal{F}$ is improper then so is $\overline{\mathcal{F}}$, and so there are fewer than $\binom{n}{2}$ elements not covered.

The reduction. Let $\phi$ be an instance of 3SAT-5 with $n$ variables and $m=5n/3$ clauses. For each clause $\phi_j$ there is a copy $\mathcal{S}_j$ of system $\mathcal{S}$. There is also a copy $\tilde{\mathcal{T}}$ of $\mathcal{T}$ in which each element is replaced by $N = 13m+1$ elements. The total number of elements is polynomial in $n$.

For each variable $x_i$ there are two sets $X_i^0$ and $X_i^1$. The set $X_i^0$ is the union of the following six sets:

the set $X_i$ of $\tilde{\mathcal{T}}$
for each clause $\phi_j$ containing $x_i$ at the first position, if $x_i$ appears positively, then the set $A_0$ of $\mathcal{S}_j$, otherwise the set $A_1$ of $\mathcal{S}_j$
for each clause $\phi_j$ containing $x_i$ at the second position, either $B_0$ or $B_1$ (as above)
for each clause $\phi_j$ containing $x_i$ at the third position, either $C_0$ or $C_1$ (as above)

The set $X_i^1$ is defined similarly as the union of the following six sets:

the set $Y_i$ of $\tilde{\mathcal{T}}$
for each clause $\phi_j$ containing $x_i$ at the first position, if $x_i$ appears negatively, then the set $A_0$ of $\mathcal{S}_j$, otherwise the set $A_1$ of $\mathcal{S}_j$
for each clause $\phi_j$ containing $x_i$ at the second position, either $B_0$ or $B_1$ (as above)
for each clause $\phi_j$ containing $x_i$ at the third position, either $C_0$ or $C_1$ (as above)

The problem is to decide whether there are $n$ sets which together cover $13m+NM$ elements (or less).

If $\phi$ is satisfiable, say with truth assignment $x_i$, then $\{X_i^{x_i} : 1 \leq i \leq n\}$ covers exactly $13m+NM$ elements. Conversely, suppose there is a way to cover at most $13m+NM$ elements. If the solution is improper then it covers at least $N(M+1) > 13m+NM$ elements (considering only $\tilde{\mathcal{T}}$). If it is proper then it corresponds to some truth assignment $x_i$, and it is easy to check that the number of elements covered is $13m+NM+Z$, where $Z$ is the number of falsified clauses. Hence $Z = 0$ and we conclude that $x_i$ is a satisfying assignment.


Adaptive vs non adaptive queries in PCP Consider verifiers in the usual sense:

Non adaptive : reads all positions of the proof predefined

Adaptive: Reads the proof iteratively.

Many lecture notes on PCP say the following:
Adaptive verifier with q queries is equivalent to non-adaptive with some q' queries where q' is a constant and both using same randomness. In other words I think this means

Non adaptive q' queries can simulate adaptive q queries. But I don't see why? How to show this?

Consider an adaptive algorithm making $q$ queries. Fixing the randomness, we can describe the positions queried by the algorithm using a function $A$ which gets as input the answers of the preceding queries, and outputs the next position to be queried. If the bits are read from an array $x$, then the adaptive algorithm works as follows:

Read $b_1 = x_{A(\lambda)}$.
Read $b_2 = x_{A(b_1)}$.
Read $b_3 = x_{A(b_1b_2)}$.
...
Read $b_q = x_{A(b_1 b_2 \ldots b_{q-1})}$.

To simulate this non-adaptively, we simply read $x_{A(w)}$ for all words $w$ of length at most $q-1$. Given these $q' = 2^q-1$ non-adaptive queries, we can simulate the adaptive algorithm.


How to find an array of probabilities that give equal products I'm trying to figure out if there is an algorithm which can solve the following:
Given an array of randomly generated values, for example: $$[54.6, 1.96, 5.0, 31.31]$$
Find an array of equal length, in this example $[x_1, x_2, x_3, x_4]$ such that:
$$54.6 \cdot x_1=1.96\cdot x_2=5.0\cdot x_3= 31.31\cdot x_4$$
and
$$x_1 + x_2 + x_3 + x_4 = 1.0$$
Any suggestions for an algorithm to solve this?

Let the array be $a_1,\ldots,a_n$, which we assume are positive. The condition $a_i x_i = a_j x_j$ implies that
$$ x_i = \frac{a_n}{a_i} x_n. $$
Since the $x_i$ must sum to $1$,
$$
1 = \sum_{i=1}^n \frac{a_n}{a_i} x_n \Longrightarrow x_n = \frac{\frac{1}{a_n}}{\sum_{i=1}^n \frac{1}{a_i}}.
$$
The formula for $x_i$ shows that
$$
x_j = \frac{\frac{1}{a_j}}{\sum_{i=i}^n \frac{1}{a_i}}.
$$


How to get samples of different paths? Say I have a "semi" directed, weighted, graph (some edges are undirected, some are directed).

Consider two nodes, A and B. Consider the set of all paths that take me from node A to node B.

I essentially want X samples of all these paths. I don't want these samples to be "too close" to the ideal path. Essentially, I want them relatively spread out over the space of solutions. I do want to include cyclic paths, which I know makes the set of possible paths infinite. Therefore, I want the paths to be relatively close to the ideal path, but still not too close. This is obviously a very vague, non-rigourous description of this aspect of the problem, which is why if possible, I would like to be able to specify some parameter that lets me control how close to the ideal my samples are.

These are the solutions I have thought of so far:

1) Use some kind of algorithm that gives me the X shortest paths. The problem with this is the samples are all too similar to the ideal path in terms of length.

2) Do the following:

     a) Run A*/Dijikstra's to find the ideal path.
     b) Remove X% of the edges that form the ideal path.
     c) Run A*/Dijistra's again to find the second sample. The fact that a portion of the edges have been removed from the ideal path, should mean that this second sample should be quite different.
     d) Remove X% of the edges that form the second sample.
     e) Repeat.

The problem with this is that I'm worried that for a large number of samples (10000+), a very large number of edges will be removed, making the samples taken later on to be very different from the ideal path.

Does anyone have any ideas on how to better approach the problem?

The graph is quite big (100000+ nodes and edges). The algorithm's speed and performance is very important, however I can do a very large amount of preprocessing beforehand, if necessary.

I can think of two approaches. Each generates a single sample at a time; any modifications to the graph are undone before generating the next sample.

Compute the shortest path, then remove r of the edges you take and generate the next-shorted path. This can be used to generate nCr samples, though many will coincide. For better quality, you probably want to also apply this to its own output: find the initial shortest path, remove 2 edges, find the intermediate shortest path, remove 2 edges, find the final shortest path. For a reasonably large graph, I would just calculate the edge(s) to remove at random in each step. Variant: instead of removing a single edge, remove both that edge and all other edges that go in/out of either vertex (I would consider the graph undirected for this step).
Randomize the weights as you pass them to A*. That is, when you advance from one node to the next, multiply that edge's weight by a number between 0.9 and 1.1 (probably with a Gaussian distribution actually). On rare occasions this might generate loops, especially if you widen the random range.


Family of types in type theory Can anyone simplify the meaning of families of types index by a type. It looks i get it but quite not understood it. What do you mean by a "family" ?

I understand index by a value (n length sequence) then what you mean by index by a type. Any example how you index by a type ? Thanks.

Consider the example of the dependent type of number sequences of length $n$. It might be defined like this in Coq:

  Inductive Sequence : nat -> Type :=
  | nil : Sequence O
  | cons : forall (n : nat), nat -> Sequence n -> Sequence (S n).

For every n : nat we have a type Sequence n. We say that Sequence is indexed by nat or that Sequence depends on nat. We could also say that Sequence n depends on the index n.

In any case, we are just discussing terminology here. The following are equiavalent ways of saying the same thing:

Type $B$ depends on type $A$
$B$ is a type family indexed by type $A$
$B$ is a dependent type indexed by type $A$
$B : A \to \mathsf{Type}$
for $x : A$, $B(x)$ is a type
$x : A \vdash B(x) \ \mathsf{type}$

The reason we use the word family is that in mathematics a collection of sets indexed by a set, $\lbrace A_i \rbrace_{i \in I}$, is called a family of sets. It corresponds to a dependent type $A$ indexed by a type $I$.


How to reduce C′A′B + CAB′ to C′B + CB′? I faced this Boolean expression:

$C'(A'B+A)+C(A'+AB')$

It was solved as follows:

$C'(A'B+A)+C(A'+AB')$
$=C'(A+B)+C(A'+B') $       ...by applying absorption laws $(I)$
$=C'A+C'B+CA'+CB'$
$=(C\oplus A)+(C\oplus B)$

However somehow it did not clicked to me to apply absorption laws. So I did following:

$C'(A'B+A)+C(A'+AB')$
$=C'A'B+C'A+CA'+CAB'$    $...(II)$

Here, I can have $C'A+CA'=C\oplus A$, but I have following doubt:

What Boolean law / identity I can use to reduce $C'A'B+CAB'$ to $C'B+CB'$ (which then can be reduced to  $C\oplus B$) ? Is it even possible? or I have to somehow remember to apply absorption law as shown above and their is not other way to arrive at $(C\oplus A)+(C\oplus B)$ by expanding as in step $(II)$?

What Boolean law / identity I can use to reduce $C'A'B+CAB'$ to $C'B+CB'$?

None.  You can't reduce $C'A'B+CAB'$ to $C'B+CB'$.  Those two Boolean expressions are not equivalent.  For example, when $A=\text{True}$, $B=\text{True}$, and $C=\text{False}$, $C'A'B+CAB'$ becomes $\text{False}$, but $C'B+CB'$ becomes $\text{True}$.


minimize sum of primes with a lower bound on product I can't quite figure out an algorithm for this:

Given some integer n, what subset of the primes (so no repeats) would yield the lowest possible sum if their product is at least n?

Example: 6 -> 2*3,

2308 -> 2*3*5*7*11,

14 -> 3*5

Does anybody know how I would do this?

This is part of a research project I'm doing on finite automata right now.

I'll suggest a very simple and very fast algorithm that I believe produces the correct result unless n is very large.

Step 1: If n = 1 the solution is {}. If n = 2 or n = 3 the solution is { n }. Otherwise, find the smallest prime p such that the product of the primes from 2 to p is ≥ n. Let S = the set of primes from 2 to p, let P = the product of the primes from 2 to p. If p < 2n then the result is S.

Otherwise, let r be the largest prime such that P / r ≥ n. Also, let q be the smallest prime > p, and let r' be the largest prime such that (P * q / p) / r' ≥ n. If r' - r > q - p then the result is S + { q } - { r', p }, otherwise the result is S - { r }.

The first n where this doesn't give the optimal solution is n = 2 * 3 * 5 * ... * 79 * 83 * 89 * 103 + 1 ≈ $2.622·10^{36}$.

Reasoning: We would want to use the smallest primes possible, because the ratio P / log p grows as p grows (with the exception of the primes 2 and 3). The exception is when we have a product that is quite a bit larger than n, and may get a product closer to n with a smaller sum.

If P < 2n, then we might replace p with a larger prime q and remove the prime 2 from the product. But q ≥ p + 2, so the sum of primes will not get smaller.

If P ≥ 2n, then removing the largest possible prime from the product will obviously make the product smaller. This does not give the optimal solution if for example P / 7 ≥ n but P / 11 < n, the next prime after p is q = p + 2, and replacing p with q in the product means that (P * q / p) / 11 ≥ n. In this case we increased the sum by 2 replacing q with p, and decreased it by 4 replace r with r'. But the algorithm will find this case.

This does not detect the case where replacing p with the next prime after q would improve the sum. Let q be the smallest prime > p, and q' the smallest prime > q. We know that q' ≥ p + 6 because p, p+2 and p+4 cannot all three be prime. So we might not find the optimal solution if the prime after r is r+8.

This is the case for the first time when r = 89 and the next prime is 97 = p + 8. If p = 101, then q = 103 and q' = 107 = p + 6. So take n = 2 * 3 * 5 * ... * 79 * 83 * 89 * 103 + 1: We need all the primes up to p = 101 to have a product P ≥ n. We can leave out r = 89 from that product, but not 97 because the remaining product is much smaller than n. If we exchange 103 for 101, we still cannot remove 97 because the product would be n-1. But we can exchange 107 for 101 and remove 97 instead of 89 from the product, getting a sum that is smaller by 2. So the optimal solution here is { 2, 3, ..., 83, 89, 107 } where the algorithm will return { 2, 3, ..., 83, 97, 101 }.


Compact Shared Reduced Binary Decision Diagrams with negated identifiers Consider a BDD implementation in which each bdd in the system has a unique positive integer identifying it (thanks to canonicity and as common implementation designs follow, by utilizing a hashmap). I was thinking of assigning a negative integer to a bdd in order to represent its negation. So say bdd id -3 will be bdd id 3 with just flipping the terminal nodes when processing them. The building blocks for new bdds would be the terminal T,F nodes, and the "ith var" bdd, where if the ith var is false then we get an id being the negation of the id of the bdd representing the ith var being true.

My question is whether such design breaks canonicity, or I can still rely on bdds having same (positive or negative) identifier to be equal.

Found the answer in the paper Shared Binary Decision Diagram with Attributed Edges for Efficient Boolean function Manipulation.

more accurate treatment can be found in section 2.3 in Proving circuit correctness using formal comparison between expected and extracted behaviour (pdf download available).

in short, canonicity is preserved if, quoting from tvandijk.nl/pdf/mscthesis.pdf page 15 "Complement edges" (The Parallelization of Binary Decision Diagram operations for model checking, thesis by Tom van Dijk):

"Minato [35] proposes the following constraints:

1) Only 0 is used as the value of a leaf.

Alternative rule 1 : only 1 is used as the value of a leaf.

Alternative rule 2 : do not allow complement edges on leaves.

2) No complement edges are allowed on 0-edges.

Alternative rule: no complement edges are allowed on 1-edges"

note that this is not a "true" restriction as if we decide that only hi edges are complemented, and we want to create a node with its lo edge being complemented, we just negate the whole node, like a?b:not(c) == not(a?not(b):c).


How to treat $\epsilon$ and '$' in top-down predictive parsing (predict table)? How to treat $\epsilon$ and '\$' in top-down parser using predict table?

The construction of the predict table

  Given a product $X \rightarrow w$, row $X$ and column $t$
  -Mark $X \rightarrow w$ for each $t \in FIRST(w)$
  -If $NULLABLE(w)$, then mark $X \rightarrow w$ for each $t \in FOLLOW(w)$ as well

says to create columns for all terminal symbols. $\epsilon$ is a terminal symbol so it's naturally added as a column.

However, I've somehow interpreted that I could/should add '\$' as a terminal symbol as well. Basically because '\$' is used in the FOLLOW sets (and the FOLLOW sets don't contain $\epsilon$).

But does this create redundancy since then the table would hold basically the same predict rules for '\$' and $\epsilon$ (at least in the implementation I have here)?

The rules given here also treat '\$' and $\epsilon$ as if they were separate:
http://www.jambe.co.nz/UNI/FirstAndFollowSets.html

The FOLLOW sets basically use '\$' in place of $\epsilon$, but the predict table uses $\epsilon$, because it's a terminal symbol.

$\epsilon$ is a terminal symbol

No.  $\epsilon$ is the empty string, i.e. no symbols at all.

  However, I've somehow interpreted that I could/should add '$' as a terminal symbol as well.

Yes, $ is the special symbol that marks the end of input, and you may have to do things at that place and when you want to go past it, you are done (or in situation of error for LR parsing if the stack is not empty).

  The rules given here also treat '$' and ϵ as if they were separate:
  http://www.jambe.co.nz/UNI/FirstAndFollowSets.html

Considering $\epsilon$ as a symbol to be put in $FIRST$ could be an worthwhile implementation trick instead of computing $NULLABLE$ separately (I haven't tried it, at first sight it seems to break useful properties and to add as much complexity as it removes, see the point 4 in the computation of $FIRST$), but it is nothing more than an implementation trick.


What is the difference between Strict 2Phase Locking and 2Phase Locking? I have read some notes about the two but yet still confused about why there is a need for the strict 2phase locking. Based on some slides,

Two Phase Locking  and  Strict Two Phase Locking

They have a single difference which is :

If transaction T releases any lock, it can acquire no new locks. <-
2PL
Hold all locks until end of transaction. <- S2PL

I will like a practical example of a Transaction in both strict and normal.Highlighting the differences.

There are mainly two reasons for adopting Strict 2PL rather than Basic 2PL, explained in [1].

The first reason is about the time when a 2PL scheduler can release some (read/write) lock owned by some transaction on some data item.
A second reason for the scheduler to keep a transaction’s locks until it
ends, and specifically until after the DM processes the transaction’s Commit or
Abort, is to guarantee a strict execution. Strict executions are recoverable and avoid cascading aborts (ACA).

[1] Chapter 3 "Two Phase Locking" in the Book "Concurrency Control and Recovery in Database Systems"; Page 59. By Bernstein et al., 1987.


Relation beetween log-space reduction and polynomial time reduction I read somewhere that given two languages A and B, if A <=(log) B, then A <=(P) B (with <=(log) the log-space reduction and <=(P) the polynomial time reduction), but I'm not sure about the proof.

Could someone help me with that please.

Thanks.

Every terminating Turing machine running in logarithmic space terminates in polynomial time. This is because the number of configurations in a logarithmic space Turing machine is polynomial; a logspace Turing machine running longer than the number of configurations will necessarily repeat a configuration, and so will never terminate.

More generally, $\mathsf{SPACE}(f(n)) \subseteq \mathsf{TIME}(2^{O(f(n))})$ for similar reasons. This gives not only $\mathsf{L} \subseteq \mathsf{P}$ but also $\mathsf{PSPACE} \subseteq \mathsf{EXPTIME}$.


Is this case of weighted 2SAT NP-complete? Weighted 2SAT asks if it is possible to satisfy the formula with at most $k$ variables set as positive/negative. Trivially, every instance must be in 2CNF. It is known to be $\mathsf{NP}$-complete.

We have following additional restriction: each variable appears twice as positive and once as negative or vice versa.

Example of instance:

$(x\lor y)\land(x\lor z)\land(\overline x\lor t)\land(\overline y\lor z)\land(\overline y\lor \overline t)\land(\overline z\lor \overline t)$

Is this weighted 2SAT variant $\mathsf{NP}$-complete?

Of course, if vertex cover where each vertex has only 2 edges is $\mathsf{NP}$-hard, this also must be $\mathsf{NP}$-hard. So, if such result is known, then it also can be an answer. Ah, well, this does not help.

You can express the predicate "$x = y$" using one occurrence of each polarity:
$$
(x \lor \lnot y) \land (\lnot x \lor y).
$$
Consider now an instance of weighted 2SAT, in which each variable appears at most $M$ times. Duplicate each variable $M$ times, and enforce that all copies are the same using the gadget above. Replace each occurrence of each variable by a distinct copy of the variable. If the original instance asks for an assignment with at most $k$ positive variables, ask for at most $Mk$ positive variables. We obtain an instance of your problem which is equivalent to the original problem.

This shows that your problem is also NP-complete.


Sorting n weight disks with decision tree I was refreshing some old tests about sorting algorithms, there was a question as follow:

Question: we have n weight disks with different weights and we want to sort them pair by pair, How many times we have to weight in worst case (maximum comparisons) to sort the whole disks?

the answer was $ \lceil \log n! \rceil $.

My issue is that I could not get to the answer and could anyone elaborate on how the answer is working?

Also one of the options was $ \lceil n\log n \rceil $, and as we know,
the order of $\log n!$ and $n\log n$ are same, So why shouldn't the
ceilings be equal too?

and How does having an ordered and distinct set of size n, matter in decision tree?

I suspect that the question is looking for a non necessarily tight lower bound to the number of comparisons needed.
The decision tree needs to be able to return the correct sorted sequence no matter what the initial permutation of the elements is. Therefore, it must have at least $n!$ leaves (one for each output permutation). Each internal vertex in the decision tree represents a comparison has has $2$ children. This means that the height of the tree must be at least $\log_2 n!$. Since the height must be an integer, you can take the ceiling.
However no algorithm can attain this number of comparisons in the worst case for all values of $n$ (notice that the intended answer does not use the asymptotic notation).
Here you can find the number of comparisons needed to sort $n$ elements for some small values of $n$. For $n=15$, $\lceil \log 15! \rceil = 41$ but $42$ comparisons are needed.
To answer your second question, $\lceil n \log n \rceil$ is incorrect since it not a valid lower bound. For example, for $n=2$, $2 \log 2 = 2$ but $1$ comparison is sufficient. You are right in saying that $O(\log n!) = O(n \log n)$ but notice how the answers are not using the big-Oh notation.
Finally, you need the discs to be linearly ordered otherwise it doesn't make sense to compare them. Moreover the fact that the input elements are distinct allows you to consider a decision tree where the outcome of each comparison is binary and is either "greater than" or "smaller than".


if (dis)proving a conjecture on graph theory can be done just by a counter example then can every (dis)proof be mapped actually to a counter-example? Suppose we have a conjecture on graph theory that can be (dis)proved by means of a counter example, then, is it true that every alternative (dis)proof of the conjecture can be mapped to a counter example?

This is in the general case, but for instance, can any proof that the hadwiger's conjecture is false be mapped to a counter example, i.e., a particular graph?

Or,

Can any proof about a purported property $P(L)$ of a language $L$, susceptible of being (dis)proved by a counter example, be mapped to a particular word, say $w$ meaning $w$ a counter example, i.e., $P(L):=FALSE\;$  since $w$ exists?

Your question isn't entirely clear, but it seems you're asking if every false graph property has a counterexample. Obviously this is true: by definition there must be some graph for which the property doesn't hold. On the other hand, a proof that the property doesn't hold for all graphs may not necessarily give an example of such a graph; this is called a non-constructive proof.


Can you substitute functions in Big-$\Theta$ notation? Say we have some function $f(n)=\Theta(\log n)$ and another function $g(n)=\Theta(n+\log n)$. Is it valid to substitute $f(n)$ for $\log n$, giving us $g(n) = \Theta(n + f(n))$? This seems obvious to me but I'm not sure if there is a weird edge case where this isn't true.

Bit $\Theta$ gives big possibilities. Let's write down what we have, assuming appropriate conditions on constants and infinity neighbourhood:
$$f(n)=\Theta(\log n) \Leftrightarrow a_1 \log n \leqslant f \leqslant a_2 \log n$$
$$g(n)=\Theta(n+\log n) \Leftrightarrow b_1 (n+\log n) \leqslant g \leqslant b_2 (n+\log n)$$
Now we combine from above inequalities
$$ c_1 (n+f) \leqslant b_1n+\frac{b_1}{a_2}f\leqslant g \leqslant b_2 n + \frac{b_2}{a_1}f \leqslant c_2 (n+f) $$
which gives $g(n) = \Theta(n + f(n))$.


Expressing functions using the arithmetic dictionary i have seen in the "logic to cs" class i take - a theorem that states: "every recursive (computable) function $f$ can be expressed using the arithmetic dictionary {$C_0, C_1, f_+(,), f_x(,), R_\le(,)$} with the structure {$D=\mathbb{N} ,C_0=0,C_1=1, f_+(a,b) =a+b, f_x(a,b)=ab, R_\le(a,b) = a\le b $}"

But we didnt prove this theorem because a part of the students didnt take the "computational models" course (i did take it though)

Where can i find a proof for this theorem? Thanks in advance!

I'm not sure this is exactly what you are looking for, but you might find what you want in Theorem 3.2.1 of Computability Theory by S. Barry Cooper:

  All recursive functions are representable in PA.

that is for any recursive function $f$, there exists a binary predicate $F$ in the language of arithmetic such that for any natural numbers $x$ and $y$ we have
$$ f(x) = y ~\Rightarrow~ \vdash_{PA} F(x,y) $$
and
$$ f(x) \neq y ~\Rightarrow~ \vdash_{PA} \lnot F(x,y) $$
where $\vdash_{PA}$ means 'PA proves'.

This theorem is central to Gödel's famous incompleteness theorem, so you might also want to take a look at ch. 8 of the mentioned book where it is discussed, and this notion of 'representability' is extended to 'semi-representability', to include the c.e. sets as well.


Reinforcement learning without self-play Self-play seems to be very important for reinforcement learning algorithms. Can we train reinforcement learning algorithms without self-play (or learn mostly from past experiences)?

For example, let's say that I want to build a TRPG AI, which involves natural language and physical interaction between heterogeneous players. I can't do self-play this game so many times. But I happen to have a lot of match log of past human games.

Can I achieve higher score than humans using reinforcement learning using these logs (maybe like Experience Replay)?

If you have a sane reward function and sufficient examples you can train a neural network on predicting your next state/value given a state/action and then use this neural network as a model to generate many more training examples on which to train a policy by selecting new action combinations.  This may result in unexpected behaviour if you do not have sufficient examples which is quite likely to occur unless you have a very large training set.

Reading up on Actor-Critic reinforcement learning may help you here.


What are good resources for self teaching parallel/concurrent/multithreaded programming techniques? I’m having a hard time finding anything thorough. I have found some courses with titles like "parallel and concurrent programming in Java", but I'm looking to learn general techniques, not their use in {insert specific technology}.

IMHO the best way to learn parallelism/concurrency is to learn how it is done in FP languages and then look for the ways to do the same in {your beloved one}. My own list:

Communicating sequential processes and Communicating Sequential Processes (CSP), by C. A. R. Hoare (PDF Version)
Erlang and books on Erlang/OTP
Parallel and Concurrent Programming in Haskell
Structured Parallel Programming Book


How to explain a language with modulo conditions is regular? I don't want to create a duplicate question of How to prove a language is regular?, I only want to know what is a good and simple way to explain why a language like

$\qquad \displaystyle L = \{w \in \{a,b,c\}^* \mid w = ua \text{ and } |u| \equiv 2 \pmod 3  \}$.

is regular.

The easiest way is by giving a regular expression for $L$:
$$
L = (a+b+c)^2((a+b+c)^3)^*a.
$$
Here $(a+b+c)^2$ is a shorthand for $(a+b+c)(a+b+c)$, and $(a+b+c)^3$ is a shorthand for $(a+b+c)(a+b+c)(a+b+c)$.

Other ways described in the comments:

Give a DFA (6 states) or an NFA (4 states) for $L$.
Decompose $L = L' a$ and give a DFA (3 states) or an NFA (3 states) for $L'$.


Does Ford-Fulkerson always produce the left-most min-cut When using Ford-Fulkerson to find max-flow between s and t, the exact choice of flow-graph depends on which paths are found.

However, if you then use the left-over residual graph to produce a min-cut (by flood-filling outward from s along any edges or reverse edges with left-over capacity), it seems the same cut is obtained regardless of which flow-graph you use.

Is this true?

Is there a way to iterate over all cuts such that each iterator-step requires only polynomial time?

Yes, Ford-Fulkerson always finds the cut that is "closest" to the source.  See this question for a formalization of what is meant by "closest".

A graph can contain exponentially many min-cuts, so beware that any procedure to enumerate all min-cuts must take exponential time in total in the worst case.

Based on what I've read, there are output-sensitive algorithms to enumerate all min $(s,t)$-cuts.  After a single maximum flow computation, the running time is $O(n)$ per min-cut that is output.  Details can be found in the following paper:

Jean-Claude Picard, Maurice Queyranne.  On the structure of all minimum cuts in a network and applications.  Combinatorial Optimization II: Mathematical Programming Studies, volume 13, 1980, pp.8--16.
Unfortunately, there does not seem to be a non-paywalled online version of the paper.

(See also here for a related question.)

In contrast, if you want to find all min-cuts of an undirected graph, rather than all min $(s,t)$-cuts, you can use Karger's algorithm to do that efficiently (in polynomial time).


Is this adjustment to an rms calculation valid? I want to calculate the RMS AC value of a signal made up of several thousand readings every second. The processor that I am using doesn't have enough memory to store a whole second of data, so I want to calculate it the sum of squares the fly.
This is the normal formula to calculate the RMS AC value, where you have to know the mean for the whole second before you can calculate the RMS:

ac_rms = sqrt (sum(square(reading-mean)) / n)

Would I get the same result if I instead use the mean from the previous second, and then apply a correction afterwards?

ac_rms = sqrt (sum(square(reading-prev_mean)) / n) - abs(mean - prev_mean)

You're looking to compute the rolling standard deviation (i.e., a streaming/online algorithm for the standard deviation).  The standard method is to use Welford's method, or a variation.
For the standard deviation, see https://jonisalonen.com/2014/efficient-and-accurate-rolling-standard-deviation/.  This is a minor adjustment to Welford's method (which computes the running variance) to reflect that you want the standard deviation rather than the variance.  See also https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance.


Parity Hamiltonian path problem Wikipedia says that Hamiltonian path problem is NPC, but Parity Hamiltonian path problem (i.e., is there an odd amount of hamiltonian path) is P. Does a reduction from, e.g., SAT, to HPP, unavoidably duplicate some solutions?

As far as we know, there is no polynomial-time algorithm for HPP. Put differently, there is no known polynomial-time reduction from any NP-hard problem with the properties that you require to Parity-HPP.

If such a reduction did exist, we could reduce any NP-hard problem A to Parity-HPP (in polynomial time) and then solve A using the polynomial-time algorithm that you claim.


Why don't we scale the cost of memory access when analyzing runtime of algorithms? Runtime for many programming languages is typically analyzed either assuming each operation takes a constant amount of time, or assuming each operation takes a logarithmic amount of time in the size the the data being manipulated. From a practical perspective, this is reasonable since modern computers have essentially constant time memory access (albeit for a fixed amount of memory).

However, from a theoretical perspective, it seems to me that this is a bad assumption.

Since bits can't be stored denser than the Planck scale (which we are fast approaching), the number of bits we can store in a certain volume of space can grow at most linearly as volume grows. Further, since the speed of memory retrieval and storage is bounded by the speed of light, it makes a lot of sense to say that as the size of the data we store grows, the cost for storing and accessing it should grow. For instance, one could assume that storing and accessing the $n$th bit of data requires $\sqrt[3]{n}$ time. (Since space is 3-dimensional).

Presumably this has been discussed in the literature somewhere. Could anyone point me to some references? Have algorithms been analyzed using this model?

You are totally right in your observation. If complexity analysis would be done on a Turing machine level the memory distance would be taken into account. You may use a 3 dimensional tape if you like and your analysis is on sub-polynomial level.

My Master thesis in 1990 was about the same topic. In that thesis I argued that instead of looking at the number of transistors/gates we should look at the length of the wires. Looking at it that way some seemingly smart ideas to reduce complexity break down. One example I used was Lupanov's method to represent an arbitrary function in a circuit taking $O(\frac{2^n}{n})$ gates. This is actually not much more efficient than a regular ROM when the average length of the wires is taken into account.

Things can get worse. If you consider a RAM machine where registers can be addressed from another register (pointers) and multiplication can be done in unit time, then it has been shown that PSPACE problems can be solved in polynomial time. I don't have a reference at hand, it was folklore at the time of my college years.

In answer to the question below. The crux of the method consists of (ab)using the fact that all registers are initially zero and the pointer arithmetic is used to leave the majority of registers at 0 and sparsely put a value in others. The registers now serve as a huge lookup table, without the burden of initializing the table.

On the wiki page for Pointer machine you will find a quote from Peter van Emde Boas:

  an interesting theoretical model, but ... its attractiveness as a fundamental model for complexity theory is questionable. Its time measure is based on uniform time in a context where this measure is known to underestimate the true time complexity. The same observation holds for the space measure for the machine (van Emde Boas (1990) p. 35)

The referred book of Van Leeuwen most likely describes the method to solve PSPACE problems on these machines in polynomial time. You may actually want to check, because it is quite some time ago for me and the machine might also need the parallelism of the PRAM model.


Is the language that consists of machine configurations whose language is a subset of even palindromes semi-decidable? Let $PAL = \{ww^R\ | w\in\{0,1\}^*\}$.

Then let $A = \{\langle M\rangle \ | \textit{M is a Turing Machine and } L(M)\subseteq PAL\}$

Is A semi-decidable (Turing recognizable or recursively enumerable)?

My try!

I said it is so here is my proof, tell me if I am way off base or tell me if A ought not to semi-decidable in the first place.

$\underline{Proof}$

A is semi-decidable by The Certificate Theorem, which states that:

If $A\subseteq\Sigma^*$ then $A\in SD$(semi-decidable) iff there is some decidable relation, $R\subseteq \Sigma^* \times \Sigma^*$, such that $\forall x\in\Sigma^*$, $x\in{A}$ iff $\exists y$ such that $R(x,y)$ holds.

We know that if $x\in{A}$ that means that $x=\langle M\rangle$, so we can choose $y = \langle M,w\rangle$ where $w\in{PAL}$. What we know is that when $M$ takes $w$ as an input it will accept (since we choose $w$ as an input), if that is the case then $w\in{L(M)}\subseteq{PAL}$. That means that $A\in{SD}$. QED

Any help would be greatly appreciated, have a great day!

What you have shown is that the language of Turing machines accepting at least one even palindrome is semi-decidable. However, your question is interested in the language of Turing machines accepting only even palindromes, which is rather different. The complement of this language is the language of Turing machines accepting at least one word which isn't an even palindrome, and so the complement is semi-decidable according to your argument. This still leaves open the question of whether the original language is semi-decidable (and so decidable).


Is polynomial over x with real roots decidable? Today while I'm looking at definition of Algorithm from Sipser's textbook, he defined the following language:
$$D_1 = \{ p \mid\ p\text{ is polynomial over }x\text{ with integral roots}\}$$.
This language is decidable since we can bound the integral roots between two values and we can try all possible values between these two numbers.
Now, I'm thinking about a the following language:
$$D_{1}^* = \{ p \mid\ p\text{ is polynomial over }x\text{ with }\mathbf{real}\text{ roots}\}$$
Is this language $D_{1}^*$ decidable? I don't think so since we have an infinite number of solutions between any two numbers in real numbers. Is my argument correct?

Maybe I should summarize what I was saying in the comments.
Yes, the problem should be formulated precisely in order to give an answer.
About the cases in which the answer is NO:
For those formulations in which the answer is NO it is usually for a trivial reason. For example, one case that is mildly interesting is if we are considering the polynomials with coefficients that are computable numbers. These are numbers for which there is an algorithm such that for any given precision it terminates and gives you the digits of the number up to that precision. So, the input of $D_1^*$ in that case, would be a finite collection of such algorithms, one for each coefficient. Well, in this case $D_1^*$ cannot be decided, even for a constant polynomial. This is just because we cannot tell if that constant is zero or not.
The context in Sipser's book:
Now, I looked at the book by Sipser. They mention $D_1$ in the context of the Hilbert's tenth problem, which concerns polynomials (in several variables) with integer coefficients. In this context and many others you can indeed decide $D_1^*$.
The interesting part:
If the coefficients are such that we can (algorithmically) perform the following operations:

sum, subtraction, multiplication, division,
test if positive, test if negative, and test if zero.

Then we can decide if a polynomial has a real root.
For example, we can consider $D_1^*$ as a problem about polynomials with integer coefficients, or rational numbers, or constructible numbers, or algebraic numbers, or perhaps consider the problem with arbitrary real numbers but in a Blum-Shub-Smale machine instead of a Turing machine. As long as we can do the six basic operations above, we should be okay.
One way to decide could be using Sturm's theorem. Sturm's theorem says that the number of real roots of a square free polynomial with real coefficients in an interval $(a,b]$ is equal to the difference of the number of changes of sign at $a$ and the number of changes of sign at $b$ of the values of a Sturm sequence. See in the link above.
If the polynomial input $p$ has complex coefficients we can just work with the $\gcd$ of its real and imaginary parts. If the polynomial is not square-free, then we divide it by the $\gcd(p,p')$ to make it square-free. These transformations don't preserve the answer. Remember that one can compute $\gcd$ using using the Euclidean algorithm. So, we only need the arithmetic operations mentioned above.
One way to construct a Sturm sequences is the following: The first term is $p$, the second term is $p'$, the derivative of $p$. If $q_i,q_{i+1}$ are two consecutive terms of the sequence constructed so far, then the next term $q_{i+2}$ is equal to the remainder of $q_{i}$ divided by $q_{i+1}$ and with the sign switched. This procedure is always finite since remainders always have smaller and smaller degrees.


Complexity bound on $RP^{RP}$ This is a homework question, I'm wondering if anyone could help.  Recall $RP$ is the set of languages recognized by randomized algorithms in polynomial time.  The question is given an algorithm in $RP$ allowed to consult an oracle in $RP$, prove the "lowest complexity bound" for a set recognized by this algorithm.

I don't think this is a very good question, it's not clear exactly what is meant by lowest complexity bound.  I suppose this means any set in this class ($RP^{RP}$) must fall in which complexity class..that is, find the lowest such one and prove it.

Any ideas?

Hint: For BPP it is the case that $BPP^{BPP} = BPP$. The idea is that given a machine in $BPP^{BPP}$, we simulate each oracle call by a BPP computation, amplified so that the error probability is very small. Since there are only polynomially many oracle calls, overall the error coming from miscalculating the BPP oracle calls is small, and the resulting machine still has bounded error. (For a more complete proof, use your web search skills.) Try to emulate this line of reasoning for RP.


Is there any language for which $\overline{L^*}=\big(\overline L\big)^*$? This question was asked in peter linz exercise. I have tried languages such as $\phi,\epsilon,\Sigma^*$.

No, thanks for Ariel's correction, since for every $L$ it holds that $\epsilon \not\in \overline{(L^*)}$  and $\epsilon \in (\overline{L})^*$ and therefore $ \overline{(L^*)}\neq (\overline{L})^*$


Sum to a certain value of a group of integers Take a group filled with an arbitrary number of random integers. Is there any way of finding out whether it is possible for the sum of the integers can equal a certain number, with the condition that any of the integers can (but do not have to) be multiplied by 0 or -1?

The only possible solution I could think of was to have the algorithm test all possible sums with each integer multiplied by 0 or -1, but this seems to be extremely inefficient, especially with larger groups of integers.

Example:

  2 40 6 7 6 2 can sum to 30 ([0*2] [40] [-1*6] [0*7] [-1*6] [2])

This is basically the subset sum problem, which is well-studied.  In particular, there is no efficient algorithm for solving all instances of this problem.

There's a small twist in your version of the problem: you allow multiplying numbers by -1.  However, your problem can still be reduced to the subset problem, by simply appending the negation of all numbers in your list to the list; then you have an instance of the subset sum problem.  For instance, if your list is 2 40 6 7 6 2, you ask whether a subset of 2 40 6 7 6 2 -2 -40 -6 -7 -6 -2 can sum to 30.  That's an instance of the subset sum problem.

If the numbers are not too large, you can use the standard dynamic programming algorithm, and it will be pretty efficient.  But this fails if the numbers are large.


Link utilization of sliding window protocol Before I ask my doubt I would like to state that problem which led me to my doubt. It can also serve as a good example scenario.

  A $20\ Kbps$ satellite link has a propagation delay of $400\ ms$. The transmitter employs the "Sliding Window protocol" scheme with Window Size set to $10$. Assuming that each frame is $100$ bytes long. What is the link utilization of transmission medium.

From the question we can make out that Window Size $(WS)$ is $10$, transmission time $(T_t)$ of a frame is $40\ ms$ , and propogation time $(T_p)$ is $400\ ms$.

Now, the solution that book proposes simply states that Link Utilization $(LU)$ for sliding window protocol can be calculated as

$$LU = \frac{WS*T_t}{T_t + 2*T_p}$$

That's where I'm facing the problem. From what I have learned about Link utilization

  It is the fraction of total time the host was busy in transmission of data. In other words, it is the ratio of total transmission time over Total Time involved in transmission.

Now if I try to fit the formula proposed in book with what I have learned, the total time involved in transmission is $T_t+2*T_p$.

But that is only the total transmission time of one single packet over the medium. Why isn't it is $WS*T_t + 2*T_p$, since we are sending $WS$ packets without wating for acknowledgement.

The only thing I could figure out after thinking a lot about my doubt is that I am probably going wrong because of my incomplete understanding of what Link Utilization means.

I will appriciate any kind of help.

Link utilitization is about the steady state, i.e., what happens when you send a lot of data... not what happens at startup (at the very beginning of the connection).

Imagine you have a humongous file to send.  It takes far more than 10 frames to send the entire file.  Calculate the total time to send the entire file.  Calculate the total transmission time for that file.  Now divide.

Try doing that calculation again.  I think you'll see that you get a  different answer.  For instance, try calculating what happens if you send a file that is 1000 frames long... or 10,000 frames long.  How long does it take to send the entire file?  What fraction of that was spent in transmission time, as opposed to waiting for acknowledgements?


What's the difference between Row Polymorphism and Structural Typing? The definitions I've stumbled across seem to indicate they express the same idea. That's that the relationship between record types is determined by their fields (or properties) rather than their names. Their Wikipedia pages also seem to indicate the same idea:

A structural type system (or property-based type system) is a major class of type system in which type compatibility and equivalence are determined by the type's actual structure or definition and not by other characteristics such as its name or place of declaration.

In programming language type theory, row polymorphism is a kind of polymorphism that allows one to write programs that are polymorphic on record field types (also known as rows, hence row polymorphism).

Are there any differences between them?

Structural type systems don't necessarily have anything to do with records. For instance, you could have a system where:
data Bool = False | True
data Two = Zero | One

are actually the same type, because they are both types with two nullary constructors. It also doesn't necessarily tell you much about records, because even though types are determined by their structure, the two records:
{s : S ; t : T}
{s : S ; t : T ; u : U}

are not the same structure, so you could have structural typing without there being anything convenient about these two types.
Similarly, row polymorphism in isolation doesn't tell you much---just that you can quantify over rows, and probably use them with e.g. a record type parameterized by a row. But there are all sorts of variations on what you can do with rows that really specify the capabilities of the system.
Usually with structural records people at least want subtyping. That allows you to say that my second record type above is a subtype of the first, so that you can pass the latter to anything expecting the former. A typical way to do this with row polymorphism is to instead quantify over the extra fields that may be present, and use some kind of row concatenation.
So perhaps a more targeted question is what is the difference between subtyping and quantifiers. The answer to that is generally that subtyping cannot express quantified types unless the quantified variable only occurs exclusively covariantly or contravariantly. So we could say:
(forall a. a -> T) ~= Top -> T
(forall a. T -> a) ~= T -> Bot

But for a type like forall a. a -> a, there is no one type to pick for a without losing information.
This extends to systems with just record subtyping vs. (appropriate) row polymorphism. However, if you have a system with subtyping and quantifiers, and subtyping can apply to quantified types, then the differences might be a lot more subtle. Having both quantifiers and subtyping can get quite tricky, though (not that row polymorphism is easy to get right, either).


Complexity of sorting a 1-sorted array A $k$-sorted array is one in which every element is at most distance $k$ from its position when the array is sorted.  The complexity of sorting such array is $O(n\log k)$. But if $k=1$, then $\log k=0$ so what happens? What is the complexity of sorting an array where each element is at most one place away from its sorted position?

When we say an algorithm runs in $O(\lg k)$ time, that is an asymptotic statement.  It means that there exists a constant $c$ such that when $k$ is sufficiently large, the running time is $\le c \lg k$.  It says nothing about what happens when $k$ is small.

In particular, if we say an algorithm runs in $O(\lg k)$ time, that doesn't necessarily mean that when $k=1$ the running time is 0.

The same kind of comment applies to your question as well.  No, it doesn't mean that the running time to sort an array where each element is at most one place away from its sorted position is $O(0)$.  Rather, the complexity of that task is $O(n)$.


Interval Scheduling Problem with more than One Resource Consider the interval scheduling problem, see also here.

In order to schedule the $n$ job requests over one resource, you sort the requests in order of finish time, choose the request with earliest finish time, choose the next compatible one, and so on.

Now, let us say we have two resources instead of one. How do I schedule my jobs now? As my idea goes, again you start by sorting the requests in order of finish time. My problem is, how do I proceed after that? Do I choose the resources in sequential or in an alternate fashion?

If I go for sequential manner, I schedule all the possible jobs in the first resource and then do the same for second resource with the jobs yet to be scheduled.

If I go for alternate fashion, I choose the first possible job in the first resource, then second possible job in the second resource and so on.

In each case we will have take in to account the chosen jobs being compatible, needless to say.

I can not decide which of these is going to be optimal.

Any input will be appreciated.

Plot the intervals for all the jobs (sorted by earliest finishing time) on the x axis. Start with y = 1.

If two jobs overlap, then plot the intervals of the later job on a higher y -- i.e.,  above the already plotted job interval. Stop when all jobs have had their intervals plotted. Sort the levels such that the bottom most level has the maximum number of jobs and the top most level has the least number of jobs.

Now, start at the lowest bottom most level of your plot (i.e., y = 1). Allocate all the jobs at this level to machine 1. Then move to y = 2 and allocate all these jobs to machine 2. Repeat till all available machines have jobs.

The number of jobs that can be allocated to k machines is optimal (simple greedy exchange argument).


Longest subsequence accepted by DFA (Dynamic Prog algorithm) Problem: Given a string $s$ and a DFA $D$, compute the longest subsequence of $s$ such that the subsequence is accepted by $D$, or report that no such subsequence exists.

This problem has a runtime of $O(qn)$ where $q$ is the number of states of the DFA, and $n$ is the length of the string.

This problem is supposed to be solved using Dynamic Programming.

I can't figure out how to get a bound lower than $O(2^n)$.

My recurrence (it's $O(2^n)$ with memoization) --

Consider the string to be $A[1 .. n]$. And consider the substring $A[1 .. i]$ for $i < n$. I know the length of the longest subsequence accepted by the DFA for this substring. Next, I consider the substring $A[1 .. i+1]$.

If this substring has a longer subsequence that is accepted by the DFA, the max value is updated. If not, the max value is kept the same.
To figure out if the max value got updated, I have to search for all subsequences accepted by the DFA that have $A[i+1]$ included in them, as well as the entire substring $A[1 .. i+1]$.

This last thing can be memoized. That is, the end point of the entire substring $A[1 .. i]$ can be memoized. So when we need to check if $A[1 .. i+1]$ works, we just need to go to the next state after reading $A[i+1]$.

We can also memoize a lot of the earlier problems we solved. We memoize the pair (subsequence, end-state).

Here's an example:
Consider the string $a_1a_2a_3a_4$.

$a_1$:
Takes $O(1)$ to check. Then memoize.

$a_1a_2$:
Check $a_2$. Takes $O(1)$. Then memoize.
Check $a_1a_2$. Takes $O(1)$ as checking $a_1$ was previously memoized. Then memoize.

$a_1a_2a_3$:
Check $a_3$: Takes $O(1)$. Then memoize.
Check $a_1a_3$, $a_2a_3$: takes $O(1)$ per check, as $a_1$, $a_2$ were previously memoized. Then memoize.
Check $a_1a_2a_3$: Takes $O(1)$ as checking $a_1a_2$ was previous memoized.

$a_1a_2a_3a_4$:
Check $a_4$: Takes $O(1)$. Then memoize.
Check $a_1a_4$, $a_2a_4$, $a_3a_4$: takes $O(1)$ per check, as $a_1$, $a_2$, $a_3$ were previously memoized.
Check $a_1a_2a_4$, $a_1a_3a_4$, $a_2a_3a_4$: takes $O(1)$ per check, as $a_1a_2$, $a_1a_3$, $a_2a_3$ were previously memoized.
Check $a_1a_2a_3a_4$: takes $O(1)$ as $a_1a_2a_3$ was previously memoized.

You can add an extra parameter $s$, which represents a state of the DFA, for your dynamic programming.

Let $f(i,s)$ be the length of the longest subsequence of $A[1\ldots i]$ accepted by a DFA obtained by changing the end state of the primary DFA to $s$. Now $f(i+1,s)$ can be computed by comparing $f(i,s)$ (representing $A[i+1]$ is not chosen) and $f(i,t)+1$ (representing $A[i+1]$ is chosen) for each state $t$ that transforms to $s$ when reading $A[i+1]$.

But note, the time complexity this algorithm is not bounded by $O(qn)$ because we may have to check no more than constant $f(i,t)$'s for each computation. A simple improvement is to consider $A[i\ldots n]$ instead of $A[1\ldots i]$. Now $f(i,s)$ represents the length of the longest subsequence of $A[i\ldots n]$ accepted by a DFA obtained by changing the start state of the primary DFA to $s$, and $f(i,s)$ can be computed by comparing $f(i+1,s)$ and $f(i+1,t)+1$ where $s$ transforms to $t$ when reading $A[i]$. Now the running time is improved to $O(qn)$.


How were weights chosen in Runge-Kutta (4) method? Consider an ODE $\dot y = f(t, y)$. We will approximate the value of $y$ using the 4th-Order Runge-Kutta method. Let $\Delta$ be the step size, then in step $i+1$ we have $~y_{i+1} = y_i + deriv\cdot\Delta~$, where:
\begin{eqnarray*}
  deriv &=& \frac{1}{6}(d_1 + 2d_2 +2d_3 + d_4) \\
    d_1 &=& f(t_i, y_i) \\
    d_2 &=& f(t_i + \frac{\Delta}{2}, y_i + d_1 \frac{\Delta}{2}) \\
    d_3 &=& f(t_i + \frac{\Delta}{2}, y_i + d_2 \frac{\Delta}{2}) \\
    d_4 &=& f(t_i + \Delta, y_i + d_3 \Delta)
\end{eqnarray*}
Why those particular weights were chosen: 2 for $d_2$ and $d_3$, and 1 for $d_1$ and $d_4$? Why not $deriv = \frac{1}{4}(d_1 + d_2 + d_3 + d_4)$? (or any other weights)

You can enter a known function that is the solution of a known differential equation, write down the Taylor series up to say 6 terms, and then substitute it into the Range-Kutta formula or any other formula.

Once you calculate it, you will find that with the Runge-Kutta formula, you add up lots of different constants which magically add up to zero. If you change the constants to what you proposed, most likely these constants add up to something that isn't zero, introducing huge errors into your solutions.


Class of the language of Turing machines that loop on at least one input $L = \{ \langle M \rangle \mid \text{there is at least one input string on which the \(M\) does not halt} \}$

Here, for a Turing machine $M$, the notation $\langle M \rangle$ denotes an encoding, over some alphabet, of the code of the Turing machine. To which of the following language classes does $L$ belong?

Regular.
Context-free but not Regular.
Recursive but not Context-free.
Recursively enumerable but not recursive.
Not recursively enumerable.

The language $L$ consists of (descriptions of) Turing machines $M$ such that $M$ does not halt on all inputs. In other words, $\langle M \rangle \notin L$ if $M$ halts on all inputs. Can you think of any connection to the halting problem?


Linear programming over a finite field I have a system of equations $Ax = b$ over some finite field $\mathbb{Z}_p$ and want to find a feasible solution. I'm sure this problem is NP-hard, but I'm struggling to find any literature on the subject. Does this problem have a name? What is known about the computational complexity of this problem?

Your problem, solving a system of linear equations, can be solved using an ancient algorithm, Gaussian elimination, which works over all fields.

Note that linear programming is more general, allowing also inequalities. It is not entirely clear, however, how the order should be defined over a finite field.


How to determine the maximum RAM capacity for an operating system? I was curious to know what limits the max RAM capacity for an OS while reading about microprocessors being 32-bit and 64-bit. I know that limit for 32-bit OS is 4GB and for 64-bit OS is 16 Exabytes, but my question is how do we get there? I found this calculation:

$\qquad 2^{32} = 4\,294\,967\,296$

and

$\qquad \frac{4\,294\,967\,296}{1024 \cdot 1024}\,\mathrm{B} = 4\,096\, \mathrm{MB} = 4\, \mathrm{GB}$.

It's different for 64-bit:

$\qquad 2^{64} = 18\,446\,744\,073\,709\,551\,616$

and

$\qquad \frac{18\,446\,744\,073\,709\,551\,616}{1024 \cdot 1024}\mathrm{B} = 16\,\mathrm{EB}$.

What I don't understand is how the calculation of bits turned into bytes and reached the results 4GB and 16EXB?

The calculation is in bytes since the memory is addressed in units of bytes. If a machine word is $N$ bits and an addressed is stored in a register whose size is a single machine word, then you can address $2^N$ different locations, each of which is a byte (in principle, that could depend on the CPU, but I'm not aware of any CPU which addresses its memory in larger words). However, more complicated addressing mechanisms can be used to address more memory. For example, pointers could take up more than a machine word, or segments could be applied (as in 80386 and its successors).


"Knapsack problem" with repetition, "lesser or equal" constraint, and recording all valid combinations In a game I am developing I came across an interesting problem, that seems like it could be solved using some modified variant of the knapsack problem, but it's a bit over my head.
Let $x_i$, $ 1\leq i \leq n$ be the objects we are dealing with, and $p_i$, $ 1\leq i \leq n$ the cost associated with each item.
Suppose there exists some total budget $B$.
I now need to find all combinations of items, such that:

the sum of their costs is lesser than or equal to the budget $B$
each object $x_j$ may appear any number of times, including not at all

This doesn't seem like a traditional optimization problem anymore, since I actually need to find all combinations that fulfill these constraints. How can this be solved efficiently? I was thinking about trying to modify the dynamic programming approach employed to solve the traditional knapsack problem, but it's a bit over my head.

The number of solutions can easily be huge, so just writing out the solutions will take a long time. But this is not the knapsack problem, which gives you a budget (knapsack capacity) and values of the items, and ask for maximal value (or if some value is atainable).
One way to generate them all is to use backtracking: List all solutions that don't include object 1, then all that do include object 1 once, twice, ... Recursively check for solutions without/with object 2, ... I don't think there can be any more efficient way, and it does prune off combinations that are doomed (can't be extended).
Look if you can narrow the search somehow. Say order the objects so that you get promising combinations early, and cut off the search when you get enough of those.


Prove np-hardness of dividing items from the lists I have the following problem.

Given a finite number of lists of items. The same item can appear in many lists. I would like to color items with 3 colors, such at least two colors appear in each list.

I would like to show that this problem is NP-hard. I would like to provide reduction from the 3-coloring problem which seems to be similar.

I think I could make items as nodes and link every item with every other from the shared lists, but then the condition of 3-coloring would be too demanding in comparison to my problem. What should I do differently in order to create the reduction?

To prove that a problem is NP-hard, we need to reduce an NP-hard problem to it (which in this case as you mentioned would be 3-coloring).

So what we are trying to do, is to map every graph $G(V,E)$ to an instance of your problem, where every node $v_i$ will be mapped with an element $el(v_i)$ and every edge $\epsilon\{v_1, v_2\}$ would be represented with a two-element list $\{el(v_1), el(v_2)\}$.

So now a coloring $f:V\rightarrow C$ would be reduced to a coloring on the set of elements in your problem which means, if we found a coloring on the elements of the proposed problem, we can use the same coloring on our graph and it would be a proper coloring.

Proof.
If $f:V\rightarrow C$ isn't a proper coloring, that means there is an edge with both nodes having the same color, which means there is a set with two elements and both of them have the same color which contradicts the statement of your problem.


Is there a simple way of calculating perceptron weights based on a classification graph? I am studying for an AI exam and I'm looking for a better way of solving the following problem:

  Graph shows a classification problem in the unit square $[0,1]^2$, where Class A
  is denoted by the grey area in the figure (not including the points on the dotted lines),
  and Class B occurs otherwise.

To solve this problem, there is a need of constructing 2 perceptrons: both perceptrons output 1 if the input lies in the grey area, and at least one of the perceptrons outputs 0 otherwise.

There are 3 ways of finding appropriate weights for inputs and biases that I know of:

Trial and error
Perceptron learning algorithm (involving random weights, learning rate, multiple epochs)
Geometrical way of finding the vectors of weights (involving finding an orthogonal line to boundary function)

All of them are quite time consuming when you do it with just pen and paper.

Is there a simple way of calculating/finding perceptron weights based on a classification graph?

think that you may be somewhat misinterpreting the point of the question. the intent of the exam question seems to be, "what good perceptron weights would result for this classification problem". the reason for this is that one cannot go through all the steps of a long-running algorithm during an exam or even homework.

so going back to perceptron theory [which is several decades old] the point is that its a classifier based on linearly separable functions, ie linear inequalities. for the 2d case this results in simple algebraic geometry. in other words the perceptron can implement some number of linear inequalities to attempt to create the classification. here it is given as $n=2$. so the question probably intended is, "what are two linear inequalities that a good perceptron algorithm would converge to for this problem".

so it seems to reduce to find the coefficients of:

$y < m_1 x + b_2$

$y > m_2 x + b_2$

so then use basic geometric algebra to determine the coefficients $m_1, m_2, b_1, b_2$ that work for the above diagram. based on the diagram there is not a perfect solution, but a "good" one. (also note that the equations only need to work within $[0,1]^2$.)

intuitively, its also somewhat implied from this analysis why perceptrons are so limited. because its easy even in 2d to draw classification problems for which there is no linearly separable solution (concave shapes, shapes with holes in them, etcetera— some hint of this is seen in noting the above shape is slightly concave). this observation, fleshed out in a more sophisticated/formal/mathematical/rigorous way in [1], caused a lot of controversy at the time & was an important debate in the history of AI, and even apparently discouraged some scientists from investigating more sophisticated simulated neural network models for some time, although Minsky emphatically denied that was his intent and said his work was misinterpreted.

[1] Perceptrons, by Minsky & Papert